_

1. 소개

평방 분할(Sqrt Decomposition)에서 Sqrt는 Square Root의 약자로, Sqrt Decomposition은 원소 \(N\)개를 \(\sqrt{N}\)개씩 묶는다는 아이디어를 사용하여 다양한 쿼리를 빠르게 처리하는 방법이다.

2. 구간 합 쿼리

N개의 수 \(A_1, A_2, ..., A_N\)가 주어졌을 때 다음 두 가지 쿼리를 처리하는 문제를 생각해보자.

1. \(x\)번째 원소를 \(y\)로 바꾼다
2. \(x\)부터 \(y\)까지 원소의 합을 구한다

Segment Tree를 사용하여 두 쿼리 모두 \(O(\log N)\)에 처리하는 방법을 생각할 수 있지만, Sqrt Decomposition을 사용하면 1번 쿼리를 \(O(1)\)에, 2번 쿼리를 \(O(\sqrt{N})\)에 처리할 수 있다.

\(\sqrt{N}\)개의 원소끼리 묶은 다음 \(i\)번째 묶음에 포함된 원소의 합을 \(B_i\)에 저장한다고 하자. 수식으로 표현하면 \(B_i = \sum_{k=1 + (i-1)\times \sqrt{N} }^{i\times \sqrt{N}} A_k\)와 같다.

1번 쿼리를 처리하는 경우 \(A_i\)와 \(A_i\)가 들어있는 \(B_j\) 두 값만 바꿔주면 된다. 이는 \(O(1)\)에 처리할 수 있다.

2번 쿼리를 처리하는 경우 \(x\)부터 \(y\) 사이에 존재하는 \(\sqrt{N}\)개 원소의 묶음이 존재하는 경우 그 원소 내 모든 원소의 합을 더해주는 대신 그에 해당하는 \(B\) 값을 더해줄 수 있다. 이렇게 묶음은 한번에 더하는 경우 더해야 하는 \(B\)는 최대 \(\sqrt{N}\)개, \(A\)는 최대 \(2\sqrt{N}\)개이므로 \(O(\sqrt{N})\)안에 처리할 수 있다.

3. Mo's Algorithm

Mo's Algorithm 참고