sqrt decomposition (평방 분할)

군대 크리스마스 기념 밀린 포스팅 작성합니다 ㅎㅇ염

사실 포스팅 몇 개 끄적이다가 귀찮아서 말듯

최근에 올린 포스팅이 segment tree인데 lazy propagation과 같은 내용도 적긴 해야하는데 귀찮아서 안 올리고 있다가 알고리즘들을 몇 개 더 배웠다.

sqrt decomposition / Mo's algorithm / Topological sort / Tarjan algorithm 순서대로 포스팅을 한 후 여태 작성하지 않은 segment tree - lazy propagation을 작성하려 한다. 

이후에는 내가 string algorithm을 공부를 하~~~~~나도 안해서 하려고 한다. (regular expression 짱짱맨)

-----------------------------------------------------------------------------------------------------

sqrt decomposition은 $O(\sqrt{N})$에 쿼리를 처리하는 내용이다. 이전 내용에서는 segment tree를 이용하여 $O(log N)$를 이용하여 처리하였지만 sqrt decomposition은 구현이 일단 매우 간단하고 후에 서술할 Mo's algorithm의 근간이 된다.

예를 들어 다음과 같은 쿼리를 생각해보자.

$arr[1, ... , N]$ 에 대하여 $arr[x, .. , y] >= K$를 만족하는 값은 몇 개가 되는가?

다음과 같은 $arr[1, ... N]$을 생각해보자.

arr 4 8 9 9  7 6 5 4   3 2 4 1   5 4 1 2

이를 count array로 바꿔서 생각해보면 다음과 같다.

arr   4 8 9 9  7 6 5 4   3 2 4 1   5 4 1 2

     

 i        1 2 3   4 5 6   7 8 9

------------------------------

cnt[i]  2 2 1   4 2 1   1 1 2

       

그렇다면 우리가 arr[1 , ... , 16] 중에서  5 이상인 값을 구하는 방법은,

cnt 배열에서 cnt[5 , ... , 9]까지의 합을 구하는 것과 같다.

arr[x]의 값이 1이상이고 K이하일때 이는 $O(K)$를 만족하게 된다.

하지만 cnt 배열을 square root를 이용해 sq-cnt 배열을 만들자.

   i            1 2 3   4 5 6   7 8 9

--------------------------------------

cnt[i]        2 2 1   4 2 1   1 1 2

   j               1         2           3

----------------------------------------

sq_cnt[j]     5         7          4

sq_cnt 배열은 cnt 배열을 sqrt root 시킨 후 이에 속한 cnt 배열의 합을 의미한 것이다.

이럴 경우 arr[1, ..., 16] 중에서 5 이상인 값을 구하는 방법은

sq_cnt[3] + cnt[5] + cnt[6] 이 된다.

이 때 잘 생각해보면 sq_cnt를 더하는 횟수는 $O(\sqrt{K})$를 만족한다.

또한 cnt를 더하는 횟수도  $O(\sqrt{K})$를 만족하므로  총 $O(\sqrt{K})$ 번만 더하면 된다.

arr[ 2, ... , 16] 중에서 구할 때는

arr[1]의 값인 4에 대해 cnt[4] 값을 -1 update 시키고, sq_cnt[2] 값을 -1 시키면 된다.

이 과정도  $O(\sqrt{K})$를 만족한다.

      

예시 코드는 Mo's Algorithm에서 설명하도록 하겠다.