평방 분할 기법 (Square Root Decomposion Technique)

Square Root Decomposition

---

우리 말로는 평방 분할(Sqrt Decomposition)이라고 불리는 이 기술은 특정 구간에 대한 질문(query)에 빠르게 답하기 위한 최적화 기술(일종의 자료구조)이다. 먼저, 아래와 같은 문제에 대해 고민해보자.

원소의 개수가 \(n\) 개인 배열 arr[]이 있다. 이 배열에 대해서 \(q\) 개의 질문(query)이 하나씩 들어온다. 질문의 내용은 다음 2가지 중 하나이다. 특정 구간 [\(l, \ r\)] 의 합을 구하라. 특정 위치 \(idx\) 의 값을 \(val\) 로 변경하라.

위와 같은 문제는 단순하게 반복문을 이용하여 \(l\) 부터 \(r\) 까지 순회하면서 값을 더해나가면 구할 수 있다(시간복잡도: \(O(q \times n)\)). 그런데 \(q\) 개의 질문에 대한 답을 하다 보면, 이미 예전에 계산해두었던 어떤 구간의 합을 또다시 계산하는 상황이 나오기 마련이다. 평방 분할 기법은 이러한 중복 계산을 최소화하는 방법을 제공한다.

평방 분할 기법의 핵심 아이디어는 아래와 같이 크기 \(n\) 의 배열을, 크기 \(\sqrt {n}\) 의 여러 블록으로 나누어, 각 블록에 해당하는 구간 합을 미리 계산해두고, 구간 [\(l, \ r\)]의 합을 계산할 때 \(l\) 과 \(r\) 사이에 완전히 포함되어있는 블록들에 해당하는 구간은 미리 계산해두었던 구간 합을 바로 사용하여 불필요한 중복 계산을 없애는 것이다.

시간복잡도를 계산해보면, 구간 합을 구하는 질문에 대해서 구간에 완전히 포함되는 블록에 해당하는 구간 합을 구하는데 \(O(\sqrt{n})\) (최대 \(\sqrt{n} + 1\) 개의 블록이 사용되기 때문)이 소요되고, 포함되지 않는 구간을 직접 순회하면서 계산하는데도 \(O(2 \times \sqrt{n})\)의 시간이 소요된다. 그리고 특정 위치 값을 갱신하는 작업의 경우 간단하게 배열 값과 해당하는 블록 값만 변경하면 되므로 상수 시간만 소요된다. 따라서 총 \(q\)개의 질문에 대한 전체 시간복잡도는 \(O(q \times \sqrt{n})\)이 된다.

int arr[MAX_N];
int block[MAX_SQRTN];
int blkSz;

void preprocess(int input[], int n) {
    int blkIdx = -1;
    blkSz = sqrt(n);

    for (int i = 0; i < n; i++) {
        arr[i] = input[i];
        if (i % blkSz == 0) {
            blkIdx++;
        }
        block[blkIdx] += arr[i];
    }
}

int query(int l, int r) {
    int sum = 0;
    int lb = l / blkSz, rb = r / blkSz;
    if (lb == rb) {
        for (int i = l; i <= r; i++) {
            sum += arr[i];
        }
    } else {
        for (int i = l; (i / blkSz) == lb; i++) {
            sum += arr[i];
        }
        for (int i = r; (i / blkSz) == rb; i--) {
            sum += arr[i];
        }
        for (int blkIdx = lb + 1; blkIdx < rb; blkIdx++) {
            sum += block[blkIdx];
        }
    }
    return sum;
}

void update(int idx, int val) {
    int blockNumber = idx / blkSz;
    block[blockNumber] += val - arr[idx];
    arr[idx] = val;
}

예제

• CF 785E Anton and Permutation

참고 자료

• http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/