imos-Hanbyeol Trick and its applications

 

(2023.06.11 online IHT with linear memory 문단 추가)

 

이 글에서는 imos법을 확장한 imos-Hanbyeol Trick (IHT)의 개념과 응용에 대해 설명한다.

귀여운 imos쨩의 그림이다.

imos법

imos법이란 구간 덧셈 업데이트를 빠르게 처리하는 테크닉이다. 다음과 같은 문제를 생각해보자.

 

0으로 초기화된 $N\times N$ 크기의 $2$차원 배열 $A$가 주어진다.  다음 연산을 $Q$개 처리한 후 배열을 출력하여라.

$x_1$ $y_1$ $x_2$ $y_2$ $z$: $A[x_1:x_2][y_1:y_2]$에 $z$를 더한다. (앞으로 모든 : notation은 닫힌 구간이다.)

 

나이브하게 했을 때 시간복잡도는 최악의 경우 $O(Q{N}^2)$이지만, imos법을 사용하면 $O(Q+N^2)$에 처리할 수 있다. 이에 대한 자료는 인터넷에 많이 있기 때문에 자세히 설명하지는 않겠다. 요약하면 $A$에 2차원 누적합을 적용했을 때 답이 나오도록 적절히 값을 더하고 빼면 $O(Q)$번의 덧셈으로 업데이트에 대한 정보를 모두 저장할 수 있다.

 

imos법의 강력한 점은 단순히 1차원, 2차원 뿐만 아니라 임의의 차원에 적용할 수 있다는 점이다. imos-Hanbyeol Trick은 이 사실을 최대한 활용하는 트릭이다.

 

더 귀여운 imos쨩 그림이다.

imos-Hanbyeol Trick

다음과 같은 문제를 생각해보자.

 

0으로 초기화된 $2\times 2\times \cdots \times 2$ 크기의 $N$차원 배열 $A$가 주어진다.  다음 연산을 $Q$개 처리한 후 배열을 출력하여라.

$x_1$ $x_2$ $\cdots$ $x_N$ $z$: $A[x_1:1][x_2:1]\cdots [x_N:1]$에 $z$를 더한다.

 

이 문제 역시 나이브하게 하면 $O(Q\cdot 2^N)$이지만 imos법을 잘 활용하면 $(Q+N\cdot 2^N)$에 풀 수 있다. 이를 imos-Hanbyeol Trick이라고 정의한다.

 

imos-Hanbyeol Trick을 이용한 풀이는 다음과 같다. 편의상 배열의 인덱스를 비트마스크로 관리하고 있다는 점에 유의하여라.

vector<int> imos_hanbyeol_trick(int N, int Q, vector<pair<int, int>> query){
    vector<int> A(1<<N);
    for (int i=0;i<Q;i++){
        A[query[i].first] += query[i].second; // imos법 처럼 값을 더해준다.
    }

    for (int i=0;i<N;i++){ 
        for (int j=0;j<(1<<N);j++) if (j&(1<<i)){
            A[j] += A[j^(1<<i)] // imos-hanbyeol trick
        }
    }
    return A;
}

코드를 보면 뭔가 우리가 알던 imos법과 다르다는 느낌을 많이 받을 것이다. 코드가 정확히 어떻게 작동하는지 알아보자.

놀란 한별이

이중반복문을 돌기 전의 배열 $A$를 $A^{\prime }$라고 하자.

$i=0$루프를 돌고 나면 $A[s0]=A^{\prime }[s0]$, $A[s1]=A^{\prime }[s0]+A^{\prime }[s1]$이 된다. ($s$는 비트스트링이다.)

$i=1$루프를 돌고 나면 $A[s00]=A^{\prime }[s00]$, $A[s01]=A^{\prime }[s00]+A^{\prime }[s01]$, $A[s10]=A^{\prime }[s00]+A^{\prime }[s10]$, $A[s11]=A^{\prime }[s00]+A^{\prime }[s01]+A^{\prime }[s10]+A^{\prime }[s11]$이 된다.

 

귀납적으로, $i$번째 루프까지 돌고 나면 $A[msk]$에는 $msk$의 하위 $i$개 비트가 submask고 상위비트는 모두 일치하는 모든 마스크에 대해, 해당되는 배열의 값을 더한 값이 저장됨을 알 수 있다. 식으로 적으면 다음과 같다.

$$A_i[msk]=\sum _{submsk\subseteq msk,(msk\oplus submsk)\subseteq (2^i-1)}{A}^{\prime }[submsk]$$

 

식 정리를 해보면 식이 잘 맞아떨어진다는 것을 확인할 수 있다. 따라서, $i=N-1$루프까지 돌고 나면, $A$에는 다음 값이 저장되어있다.

$$A[msk]=\sum _{submsk\subseteq msk}{A}^{\prime }[submsk]$$

$ms{k}^{\prime }$ $z$에 해당하는 업데이트는 $ms{k}^{\prime }$을 submask로 가지는 모든 $msk$에 $z$를 더하는 업데이트이므로, 최종 상태의 $A$는 구하고자하는 $A$와 동일하다.

 

놀라운 사실은, 우리가 지금까지 계산한 것이 imos법과 정확히 동일하다는 사실이다! 상상하기 힘들지만, $N$개의 축을 가진 $N$차원 공간의 초직육면체를 생각해보자. ($N=3$정도로 놓고 8개의 값이 어떻게 변하는지 생각해보면 좀 더 편하다.) $i$번째 루프를 도는 행위는 imos법에서 $i$번째 축으로 스위핑하면서 누적합을 해주는 것과 동일하다는 것을 알 수 있다. 즉, imos-Hanbyeol Trick은 $N$차원 imos법을 비트마스킹을 이용해서 간단하게 구현한 것이다.

 

imos-Hanbyeol Trick을 다르게 표현하면 배열 $A$가 주어질 때 다음 배열 $B$를 빠르게 계산하는 것이다.

$$B[msk]=\sum _{submsk\subseteq msk}A[submsk]$$

havana723님이 그리신 귀여운 imos쨩과 한별이의 그림이다.

Online imos-Hanbyeol Trick

다음과 같은 점화식의 dp를 생각해보자.

$$dp[msk]=f(\sum _{submsk⊊msk}dp[submsk])$$

$f$는 상수시간에 계산할 수 있는 함수라고 가정하자. imos-Hanbyeol Trick은 쿼리/값을 모두 받고 한번에 처리하기 때문에 이처럼 online 꼴의 점화식을 계산할 수 없다는 한계점을 가지고 있다. 그러나, imos-Hanbyeol Trick을 돌릴 때 나오는 값들을 잘 활용하면 이를 계산하는 것이 가능하다.

 

imos-Hanbyeol Trick을 증명할 때 사용한 식을 가져와보자. 앞에서 설명했듯이, 하위 $i$개 비트에 대한 submask들의 합이다.

$$S_i[msk]=\sum _{submsk\subseteq msk,(msk\oplus submsk)\subseteq (2^i-1)}dp[submsk]$$

이를 이용하면 $dp[msk]$를 다음과 같이 적을 수 있다.

$$dp[msk]=f(\sum _{2^i\wedge msk\ne 0}{S}_i[msk\oplus 2^i])$$

따라서, $S_i[msk]$에 대한 정보가 있다면 $dp$를 $O(N\cdot 2^N)$에 구할 수 있다.

 

한편, $S_i[msk]$의 정의를 잘 생각해보면 $S_i[msk]$에 대한 점화식도 쉽게 구할 수 있다.

$$S_i[msk]=\{\begin{array}{ll}{S}_{i-1}[msk]& (\text{if}msk\wedge 2^i=0)\\ S_{i-1}[msk]+S_i[msk\oplus 2^i]& (\text{if}msk\wedge 2^i\ne 0)\end{array}$$

편의상 $S_{-1}[msk]=dp[msk]$로 정의하면 편하다.

 

이를 코드로 구현하면 다음과 같다. 시간복잡도는 $O(N\times 2^N)$이다.

 

vector<int> online_imos_hanbyeol_trick(int N){
    vector<int> dp(1<<N, 0);
    vector<vector<int>> S(1<<N, vector<int>(N, 0));

    for (int msk=0;msk<(1<<N);msk++){
        for (int i=0;i<N;i++) if (msk&(1<<i)){
            dp[msk] += S[msk^(1<<i)][i];
        }
        dp[msk] = f(dp[msk]);

        for (int i=0;i<N;i++){
            if (i) S[msk][i] = S[msk][i-1];
            else S[msk][i] = dp[msk];

            if (msk&(1<<i)) S[msk][i] += S[msk^(1<<i)][i];
        }
    }
    
    return dp;
}

Online imos-Hanbyeol Trick with linear memory

이 파트는 sait2000님의 도움을 받아 작성되었습니다.

웰노운 아니야

Online imos-Hanbyeol Trick을 나이브하게 짜면 공간복잡도 $O(N\cdot 2^N)$이 되지만, 값 갱신을 적절하게 해주면 공간복잡도 $O(2^N)$으로 짤 수 있다! 메모리를 대략 /20 해주기 때문에 메모리를 매우 아낄 수 있고, 시간도 꽤 줄어드는 꽤나 강력한 최적화라고 볼 수 있다. 일단 코드부터 보자.

vector<int> online_imos_hanbyeol_trick_linear_memory(int N){
    vector<int> dp(1<<N, 0);
    vector<int> S(1<<N, 0);

    for (int msk=0;msk<(1<<N);msk++){
        for (int i=0;i<N;i++) if (msk&(1<<i)){
            dp[msk] += S[msk^(1<<i)];
        }
        dp[msk] = f(dp[msk]);
        S[msk] = dp[msk];

        for (int i=0;msk&(1<<i);i++){
            int r = msk + 1;
            int l = r - (1<<i);
            for (int msk2=l;msk2<r;msk2++){
                S[msk2] += S[msk2 ^ (1<<i)];
            }
        }
    }
    
    return dp;
}

편의상 아까 정의했던 $S_i[msk]$를 $msk$에 대한 크기 $i$의 subset sum이라고 부르자. 현재 for문에서 돌고 있는 $msk$에 대해, $msk=2^{i_1}+\cdots +2^{i_k}$ (단, $i_1>\cdots >i_k$)라고 하자. 즉, $i_1,\dots ,i_k$는 $msk$의 비트 중 켜져있는 비트들이다. 이때, $S$에 저장된 값은 다음과 같다.

 

$S[0:2^{i_1}-1]$: 크기 $i_1$의 subset sum

$S[2^{i_1}:(2^{i_1}+2^{i_2}-1)]$: 크기 $i_2$의 subset sum

...

$S[(2^{i_1}+\cdots +2^{i_{k-1}}):(2^{i_1}+\cdots +2^{i_{k-1}}+2^{i_k}-1)]$: 크기 $i_k$의 subset sum

 

따라서, 현재 상태에서 $S[msk\oplus 2^{i_j}]=S_{i_j}[msk\oplus 2^{i_j}]$가 성립하게 되고, $dp$ 점화식이 잘 계산된다.

 

식만 보면 이해하기 힘드니 예시를 들어보자. 현재 $msk=26={11010}_{(2)}$라고 하면, $S$배열에는 다음과 같은 값들이 저장되어있다. (편의상 인덱스를 다섯자리 이진수로 적었다.)

$S[00000:01111]$: 크기 $4$의 subset sum

$S[10000:10111]$: 크기 $3$의 subset sum

$S[11000:11001]$: 크기 $1$의 subset sum

 

$dp[11010]$은 다음과 같이 계산된다.

$$\begin{array}{rl}dp[11010]& =f(S[01010]+S[10010]+S[11000])\\ & =f((dp[00000]+dp[00010]+dp[01000]+dp[01010])+(dp[10000]+dp[10010])+(dp[11000]))\end{array}$$

 

이제, 남은 부분은 $S$배열을 갱신하는 부분이다. for (int i=0;msk&(1<<i);i++)에 해당하는 반복문이 바로 그 파트이다. $S$배열은 인덱스 0부터 길이 $2^{i_1}$, $2^{i_2}$, ... , $2^{i_k}$의 "블록"을 이룬다는 점에 유의하자. $msk$를 1 늘릴 때 이 블록들이 어떻게 갱신되어야하는지 살펴볼 것이다.

 

$i_k>0$이면, $2^0$짜리 블록을 추가하면 갱신이 끝나기 때문에 따로 해줄 것이 없다. (S[msk] = dp[msk])

$i_k=0$이면, 기존에 있던 $2^0$짜리 블록과 새로 추가된 $2^0$짜리 블록을 합쳐서 $2^1$짜리 블록으로 만들어줘야한다. 이때, 인덱스를 잘 생각해보면 앞에 있는 블록의 인덱스는 $2^0$에 해당하는 비트가 꺼져있고, 뒤에 있는 블록의 인덱스는 $2^0$에 해당하는 비트가 켜져있기 때문에, 뒤에 있는 블록의 값을 앞에 있는 블록의 값으로 갱신해주면 된다. 앞에 있는 블록은 $2^0$비트가 꺼져있기 때문에 크기를 늘려도 subset sum이 변하지 않는다. (S[msk2] += S[msk2 ^ (1<<i)])

 

이렇게 블록을 1번 합쳐주고나서 끝날 수도 있지만, $i_{k-1}=1$이라면 $2^1$짜리 블록이 2개가 되기 때문에 이를 또 합쳐줘야한다. 이 과정은 여러 번 반복될 수 있다. 따라서, 블록을 합치는 과정을 $i$를 0부터 늘리면서 계속하다가, $msk\wedge 2^i=0$이 되는 순간 갱신을 하지 않고 중단해줘야 한다는 것을 알 수 있다.

길이 $2^i$짜리 블록 2개를 합치려고 한다면 앞에 있는 블록의 인덱스는 모두 $2^i$에 해당하는 비트가 꺼져있고 뒤에 있는 블록은 모두 켜져있다는 사실을 이용해서 아까처럼 갱신해주면 된다. (S[msk2] += S[msk2 ^ (1<<i)])

 

따라서, S를 갱신하는 부분만 코드로 적으면 다음과 같다.

        S[msk] = dp[msk];

        for (int i=0;msk&(1<<i);i++){
            int r = msk + 1;
            int l = r - (1<<i);
            for (int msk2=l;msk2<r;msk2++){
                S[msk2] += S[msk2 ^ (1<<i)];
            }
        }

각 원소에 대해 저장된 subset sum의 크기가 최대 $N$까지 갈 수 있고, 크기를 늘리는 것은 덧셈 0번 또는 1번에 되기 때문에 $S$배열을 갱신하는 과정은 시간복잡도 $O(N\cdot 2^N)$임을 알 수 있다. 따라서, Online IHT를 시간복잡도 $O(N\cdot 2^N)$, 공간복잡도 $O(2^N)$에 할 수 있다.

OR Convolution using imos-Hanbyeol Trick (a.k.a. imos-Hanbyeol Gwabegigul)

이 파트는 koosaga님의 글(https://codeforces.com/blog/entry/115438)을 참고하여 작성되었습니다.

imos-한별 꽈배기굴의 개형도이다.

배열 $A$와 $B$가 주어질 때, $A$와 $B$의 OR Convolution $C$는 다음과 같다.

$$C[i]=\sum _{j\vee k=i}A[j]B[k]$$

나이브하게 계산하면 $O(4^N)$의 시간이 걸리지만, imos-Hanbyeol Trick을 이용해서 $O(N\cdot 2^N)$에 계산할 수 있다.

 

imos-Hanbyeol Trick을 이용하면 다음을 구할 수 있다.

$$A^{\prime }[i]=\sum _{i\vee j=i}A[j]$$

$$B^{\prime }[i]=\sum _{i\vee j=i}B[j]$$

$$C^{\prime }[i]=\sum A^{\prime }[i]B^{\prime }[i]$$

 

이때, 다음이 성립함을 알 수 있다.

$$C^{\prime }[i]=\sum _{i\vee j\vee k=i}A[j]B[k]=\sum _{i\vee p=i}C[p]$$

즉, $C^{\prime }$은 $C$에 imos-Hanbyeol Trick을 적용한 배열이다. 따라서, imos-Hanbyeol Trick을 거꾸로 해주면(Inverse imos-Hanbyeol Trick, IIHT) OR Convolution 결과를 얻을 수 있다.

 

코드는 다음과 같다.

vector<int> imos_hanbyeol_gwabegigul(int N, vector<int> A, vector<int> B){
    vector<int> C(A.size());

    // imos-hanbyeol trick
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < (1 << N); j++) {
            if (j & (1<<i)) {
                A[j] += A[j ^ (1 << i)];
                B[j] += B[j ^ (1 << i)];
            }
        }
    }

    for (int i = 0; i < (1 << N); i++) {
        C[i] = A[i] * B[i];
    }

    // inverse imos-hanbyeol trick
    for (int i = N - 1; i >= 0; i--) {
        for (int j = (1 << N) - 1; j >= 0; j--) {
            if (j & (1<<i)) {
                C[j] -= C[j ^ (1 << i)];
            }
        }
    }
    return C;
}

 

연습문제

난이도 순서가 아닐 수 있다.

https://www.acmicpc.net/problem/2803

2803번: 내가 어렸을 때 가지고 놀던 장난감

https://www.acmicpc.net/problem/25390

25390번: Traveling Junkman Problem

https://www.acmicpc.net/problem/27841(Online imos-Hanbyeol Trick으로 풀어보자.)

27841번: Problem Setting

Compatible Numbers

Bits And Pieces

Marek and Matching (easy version)

AND Convolution