제곱근 분할법 (Square Root Decomposition)

 

🔗 백준 2042번 - 구간 합 구하기 문제를 보자.

 

세그먼트 트리를 입문하면서 처음 만나게 되는 문제로 유명하다.

여기서는 세그먼트 트리를 사용하지 않는, $O(M \sqrt{N})$ 풀이를 소개하려 한다.

아이디어

원래 세그먼트 트리에선, 구간을 반씩 쪼개어 총 $O(N\log{N})$개의 구간 합을 관리하는 아이디어를 사용한다.

구간을 쪼갠다는 아이디어 자체는 같다.

 

여기서는 길이가 동일한 구간을 $O(\sqrt{N})$개 만들어서 각 구간의 길이 또한 $O(\sqrt{N})$이 되도록 관리한다.

보통 구간 하나하나를 버킷이라 칭한다.

 

 

 

적용

각 버킷별로 합을 저장하는 배열을 만들어 놓자.

만약 위 그림처럼 특정 구간의 합을 구하려고 할 때,

초록색 부분만 하나하나 직접 더해주고 파란색 부분은 미리 구해놓은 버킷 합을 이용해 구할 수 있다.

 

이 때의 시간복잡도를 계산해보자.

 

초록색 부분에 대해서, 직접 더해주는 원소의 개수는 $O(\sqrt{N})$이다.

→ 왜냐? 구간을 쪼갤 때 버킷의 크기를 $\sqrt{N}$으로 정했기 때문이다.

 

파란색 부분에 대해서, 접근하게 되는 버킷의 개수는 $O(\sqrt{N})$이다.

→ 왜냐? 전체 버킷의 개수가 $O(\sqrt{N})$이기 때문이다.

 

따라서, 쿼리 한 번당 시간복잡도는 놀랍게도 $O(\sqrt{N})$이 된다.

핵심

제곱근 분할법은 아이디어를 떠올려내기가 힘들 뿐이고, 구현 난이도는 아주 쉬운 축에 속한다.

이걸 적용할 때 주의해야 할 점은 크게 두 가지라고 생각한다.

 

1. 버킷의 정의

 

위에서 예시로 든 문제에선 각 버킷에 그 버킷이 포함하고 있는 구간의 원소 합을 저장한 것처럼, 버킷에 어떤 값을 저장할 건지 명확히 해야 한다.

 

2. 버킷 크기 지정

 

보통 나는 N = 100,000일 때 버킷의 크기를 1000으로 잡는 편이다. 위에서는 버킷 크기를 $O(\sqrt{N})$으로 적어두었지만, 사실 직접 값을 대입해보며 실행 시간이 단축될 수 있는 최적의 사이즈를 찾는 것이 최선이라 생각한다.

연습 문제

🔗 백준 14504번 - 수열과 쿼리 18

제곱근 분할법으로 해결할 수 있는 가장 기초적인 문제다.

 

🔗 백준 7469번 - K번째 수

다른 풀이가 많지만, 제곱근 분할법을 적용해볼 수 있다.

코드

백준 2042번 - 구간 합 구하기의 AC 코드이다.

import java.util.*;
import java.io.*;

class IOController {
    BufferedReader br;
    BufferedWriter bw;
    StringTokenizer st;

    public IOController() {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer("");
    }

    String nextLine() throws Exception {
        String line = br.readLine();
        st = new StringTokenizer(line);
        return line;
    }

    String nextToken() throws Exception {
        while (!st.hasMoreTokens()) nextLine();
        return st.nextToken();
    }

    int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

    void close() throws Exception {
        bw.flush();
        bw.close();
    }

    void write(String content) throws Exception {
        bw.write(content);
    }

}

public class Main {

    static IOController io;

    //

    static int N, M;
    static int bucketSize, size;
    static long[] a, b;

    public static void main(String[] args) throws Exception {

        io = new IOController();

        init();
        solve();

        io.close();

    }

    static void init() throws Exception {

        N = io.nextInt();
        M = io.nextInt() + io.nextInt();
        a = new long[N];
        for(int i=0;i<N;i++) a[i] = io.nextLong();
        bucketSize = (int)Math.sqrt(N);
        size = (N-1)/bucketSize + 1;
        b = new long[size];

    }

    static void solve() throws Exception {

        for(int i=0;i<N;i++) {
            int bucketNum = i/bucketSize;
            b[bucketNum] += a[i];
        }

        while(M-->0) {
            int op = io.nextInt();
            if(op == 1) {
                int i = io.nextInt()-1;
                long c = io.nextLong();
                int bucketNum = i/bucketSize;
                b[bucketNum] -= a[i];
                a[i] = c;
                b[bucketNum] += a[i];
            }
            else {
                int l = io.nextInt()-1;
                int r = io.nextInt()-1;
                int lNum = l/bucketSize;
                int rNum = r/bucketSize;

                long res = 0;

                for(int i=l;i<Math.min(r+1, (lNum+1)*bucketSize);i++) res += a[i];
                for(int i=lNum+1;i<rNum;i++) res += b[i];
                if(lNum < rNum) for(int i=rNum*bucketSize;i<=r;i++) res += a[i];

                io.write(res + "\n");
            }
        }

    }

}