[C++] Sqrt Decomposition 알고리즘

 

Sqrt Decomposition 알고리즘은 연속된 어떤 배열을 구간 별로 합을 bucket에 저장하여 효과적으로 구간합을 구할 수 있는 알고리즘이다. 주로 어디서 부터 어디까지 합을 구해야하는 문제에서 요긴하게 쓸 수 있다. 시간복잡도는 O( √n)으로, 보다 빠른 방법은 Segment tree 알고리즘이 있지만, Sqrt Decomposition이 상대적으로 구현하기 쉽고 Segment tree로 풀 수 없는 문제도 풀 수 있으니 꼭 알아두자.

 

예제로 백준 2042번: 구간 합 구하기를 풀어보자.

#include <iostream>
#include <math.h>
#define MAX 1'000'001
using namespace std;
typedef long long ll;
ll N, M, K;
ll Numbers[MAX];
ll Bucket[MAX];

int main() {
    cin >> N >> M >> K;
    ll sqrtNum = sqrt(N);

    for (int i = 0; i < N; ++i) {
        cin >> Numbers[i];
        Bucket[i / sqrtNum] += Numbers[i];
    }

    for (int i = 0; i < M + K; ++i) {
        ll a, b, c;
        cin >> a >> b >> c;

        if (a == 1) {
            b--;
            Bucket[b / sqrtNum] -= Numbers[b];
            Bucket[b / sqrtNum] += c;
            Numbers[b] = c;
        }
        else if (a == 2) {
            ll sum = 0;
            b--;
            c--;
            /* left & right */
            while (b % sqrtNum != 0 && b <= c) {
                sum += Numbers[b++];
            }
            while ((c+1) % sqrtNum != 0 && b <= c) {
                sum += Numbers[c--];
            }

            /* bucket */
            while (b <= c) {
                sum += Bucket[b / sqrtNum];
                b += sqrtNum;
            }

            cout << sum << "\n";
        }
    }
}

구간합을 구하는 문제는 주로 범위가 매우 크니, 자료형이 범위에 들어오는지 잘 체크하자.

위 코드를 통해 제출하면 Segment tree 방법에 비해 4배 정도 느리지만 통과하는 것을 확인할 수 있다.