제곱근 분할법 (Square Root Decomposition)

크기가 $N$인 정수 배열 $A$가 있고, 여기서 다음과 같은 연산을 최대 $M$번 수행해야 하는 문제가 있습니다.

1. 구간 $l$, $r$ ($l ≤ r$)이 주어졌을 때, $\min(A[l], A[l+1], \dots , A[r])$을 구해서 출력하기
2. $i$번째 수를 $v$로 바꾸기 ($A[i] = v$)

1번 연산 $\min(A[l], A[l+1], \dots , A[r])$을 구하기 위해 소스 1과 같이 모두 더하는 방법이 있습니다.

int ans = a[l];
for (int i=l; i<=r; i++) {
    if (ans > a[i]) {
        ans = a[i];
    }
}

int ans = a[l];
for (int i=l; i<=r; i++) {
    if (ans > a[i]) {
        ans = a[i];
    }
}

ans = a[i]
for i in range(l, r+1):
    if ans > a[i]:
        ans = a[i]

소스 1의 시간 복잡도는 $O(N)$입니다. 2번 연산 $A[i] = v$는 $O(1)$ 입니다. 연산을 최대 $M$번 수행해야 하니 연산 하나의 시간 복잡도는 $O(N)$이 됩니다. 총 시간 복잡도는 $O(NM)$입니다.

제곱근 분할법을 사용하려면 크기가 $N$인 배열을 크기가 $\sqrt{ N }$인 그룹으로 나누고, 각 그룹의 최솟값을 별도로 저장해야 합니다.

그룹의 크기가 $\sqrt{ N }$이니, 그룹의 개수도 $\sqrt{ N }$개입니다. $N$이 제곱수가 아닌 경우에는 그룹의 크기로 $\lfloor \sqrt{ N } \rfloor$를 사용합니다.

그룹의 크기는 $r$, 그룹의 개수는 $g$, $i$번째 그룹에 들어있는 수의 최솟값은 $D[i]$로 표현합니다.

$N$ = ($1 \le N \le 20$)

• 그룹의 크기 = $r$ = $\lfloor \sqrt { N } \rfloor$ =
• 그룹의 개수 = $g$ = $\lceil N / r \rceil$ =

소스 2를 이용해 $D$를 구할 수 있습니다.

int r = (int)sqrt(n);
int g = n / r;
if (n % r != 0) g += 1;
vector<int> d(g);
for (int i=0; i<n; i++) {
    if (i % r == 0) {
        d[i/r] = a[i];
    } else {
        if (d[i/r] > a[i]) {
            d[i/r] = a[i];
        }
    }
}

int r = (int)Math.floor(Math.sqrt(n));
int g = n / r;
if (n % r != 0) g += 1;
int[] d = new int[g];
for (int i=0; i<n; i++) {
    if (i % r == 0) {
        d[i/r] = a[i];
    } else {
        if (d[i/r] > a[i]) {
            d[i/r] = a[i];
        }
    }
}

r = (int)(n ** 0.5)
g = n // r
if n % r != 0:
    g += 1
d = [0] * g
for i in range(n):
    if i % r == 0:
        d[i//r] = a[i]
    else:
        if d[i//r] > a[i]:
            d[i//r] = a[i]

2번 연산은 $i$번째 수를 $v$로 바꾸는 연산입니다.

이 경우 $i$번째 수가 포함된 그룹의 $D$만 변경하면 됩니다. 그룹에 포함된 수의 최솟값을 구하려면, 그 그룹에 포함된 모든 수를 조사하면 됩니다. 그룹에 포함된 수의 개수는 $r = \lfloor \sqrt{ N } \rfloor$이니 시간 복잡도는 $O(\sqrt { N })$입니다.

소스 3과 같이 구현할 수 있습니다.

void update(vector<int> &a, vector<int> &d, int r, int index, int v) {
    a[index] = v;
    int group = index / r;
    int start = group * r;
    int end = start + r;
    if (end > a.size()) end = a.size();
    d[group] = a[start];
    for (int i=start; i<end; i++) {
        if (d[group] > a[i]) {
            d[group] = a[i];
        }
    }
}

void update(int[] a, int[] d, int r, int index, int v) {
    a[index] = v;
    int group = index / r;
    int start = group * r;
    int end = start + r;
    if (end > a.length) end = a.length;
    d[group] = a[start];
    for (int i=start; i<end; i++) {
        if (d[group] > a[i]) {
            d[group] = a[i];
        }
    }
}

def update(a, d, r, index, v):
    a[index] = v
    group = index // r
    start = group * r
    end = start + r
    if end > len(a):
        end = len(a)
    d[group] = a[start]
    for i in range(start, end):
        if d[group] > a[i]:
            d[group] = a[i]

update(a, d, r, index, v)는 a[index]에 저장되어 있는 값을 변경하고, index가 해당하는 그룹의 최솟값도 변경하는 함수입니다.

변경을 구현하기 위해 먼저, a[index]에 저장되어 있는 값을 변경합니다.

그 다음, index가 속한 그룹의 번호를 구해 이를 group에 저장하고, 해당 그룹의 첫 번째 인덱스 start와 마지막 인덱스 + 1인 end를 구합니다.

마지막으로 그룹에 들어있는 수 전체를 순회하면서 그룹의 최솟값 d[group]을 구합니다.

$\min(A[l], A[l+1], \dots , A[r])$을 구하기 방법에 대해서 알아봅시다.

다음과 같은 두 가지 경우로 나눌 수 있습니다.

1. $l$과 $r$이 같은 그룹에 속한 경우
2. $l$과 $r$이 같은 그룹에 속하지 않은 경우

같은 그룹에 속한 경우에는 그룹의 최솟값을 저장한 배열 $D$를 이용할 수 없습니다. 최솟값이 구간 $[l,r]$에 속하지 않을 수도 있기 때문입니다. 따라서, 소스 1과 같이 $l$부터 $r$까지를 순회해서 최소값을 구해야 합니다. 하나의 그룹에 포함된 수의 개수는 $r = \lfloor \sqrt{ N } \rfloor$이기 때문에, 이 경우 시간 복잡도는 $O(\sqrt { N })$입니다.

다른 그룹에 속한 경우는 그룹을 다음과 같이 세 가지 경우로 다시 나눌 수 있습니다.

1. $l$이 속한 그룹
2. $r$이 속한 그룹
3. 위의 두 그룹 사이에 있는 그룹

$l$이 속한 그룹과 $r$이 속한 그룹에서는 $D$를 이용할 수 없기 때문에, $l$부터 $l$이 속한 그룹의 끝까지, $r$이 속한 그룹의 시작부터 $r$까지 순회해서 최솟값을 구해야 합니다. 각각의 경우 모두 최대 $\sqrt{ N }$번의 비교를 해야하니 시간 복잡도는 $O(\sqrt { N })$입니다.

두 그룹 사이에 있는 그룹의 경우에는 그 그룹에 속한 모든 수가 구간 $[l,r]$에 포함되기 때문에, $D$를 이용할 수 있습니다. 그룹의 개수도 $\sqrt{ N }$개이니, 시간 복잡도는 $O(\sqrt{ N })$입니다.

시간 복잡도를 정리해보면 다음과 같습니다.

1. $l$과 $r$이 같은 그룹에 속한 경우 = $O(\sqrt{ N })$
2. $l$과 $r$이 같은 그룹에 속하지 않은 경우 = $O(3 \times \sqrt{ N })$ = $O(\sqrt{ N })$

변경도 $O(\sqrt{ N })$에 구할 수 있습니다.

소스 4와 같이 구현할 수 있습니다.

• $A = $ 로 초기화
  • $1 \le N \le 20$
  • $1 \le A[i] \le 99$

• 최솟값 구하기: $l$ = , $r$ =

int query(vector<int> &a, vector<int> &d, int r, int start, int end) {
    int n = a.size();
    int ans = a[start];
    if (start/r == end/r) {
        for (int i=start; i<=end; i++) {
            if (ans > a[i]) {
                ans = a[i];
            }
        }
        return ans;
    }
    while (true) {
        if (ans > a[start]) {
            ans = a[start];
        }
        start += 1;
        if (start % r == 0) {
            break;
        }
    }
    while (true) {
        if (ans > a[end]) {
            ans = a[end];
        }
        end -= 1;
        if (end % r == r-1) {
            break;
        }
    }
    int start_group = start/r;
    int end_group = end/r;
    for (int i=start_group; i<=end_group; i++) {
        if (ans > d[i]) {
            ans = d[i];
        }
    }
    return ans;
}

int query(int[] a, int[] d, int r, int start, int end) {
    int n = a.length;
    int ans = a[start];
    if (start/r == end/r) {
        for (int i=start; i<=end; i++) {
            if (ans > a[i]) {
                ans = a[i];
            }
        }
        return ans;
    }
    while (true) {
        if (ans > a[start]) {
            ans = a[start];
        }
        start += 1;
        if (start % r == 0) {
            break;
        }
    }
    while (true) {
        if (ans > a[end]) {
            ans = a[end];
        }
        end -= 1;
        if (end % r == r-1) {
            break;
        }
    }
    int start_group = start/r;
    int end_group = end/r;
    for (int i=start_group; i<=end_group; i++) {
        if (ans > d[i]) {
            ans = d[i];
        }
    }
    return ans;
}

def query(a, d, r, start, end):
    n = len(a)
    ans = a[start]
    if start // r == end // r:
        for i in range(start, end+1):
            if ans > a[i]:
                ans = a[i]
        return ans
    
    while True:
        if ans > a[start]:
            ans = a[start]
        start += 1
        if start % r == 0:
            break

    while True:
        if ans > a[end]:
            ans = a[end]
        end -= 1
        if end % r == r-1:
            break
            
    start_group = start // r
    end_group = end // r
    for i in range(start_group, end_group+1):
        if ans > d[i]:
            ans = d[i]

    return ans

start는 구간의 시작 $l$, end는 구간의 끝 $r$을 의미합니다.

start/r == end/r인 경우는 같은 그룹에 속한 경우입니다. 소스 1과 같은 방식으로 구현한 것을 확인할 수 있습니다.

같은 그룹에 속하지 않은 경우는 3개의 작은 부분으로 나누어져있습니다. 첫 while은 start가 속한 그룹에서 최솟값을 구하는 부분, 그 다음 while는 end가 속한 그룹에서 최솟값을 구하는 부분입니다.

이제 남은 것은 두 그룹 사이에 속하는 그룹의 최솟값과 비교하는 부분이고, 이 부분은 마지막 for입니다.

이 글의 가장 처음에 설명한 문제와 같은 문제입니다. 소스 5로 해결할 수 있습니다.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
void update(vector<int> &a, vector<int> &d, int r, int index, int v) {
    a[index] = v;
    int group = index / r;
    int start = group * r;
    int end = start + r;
    if (end > a.size()) end = a.size();
    d[group] = a[start];
    for (int i=start; i<end; i++) {
        if (d[group] > a[i]) {
            d[group] = a[i];
        }
    }
}
int query(vector<int> &a, vector<int> &d, int r, int start, int end) {
    int n = a.size();
    int ans = a[start];
    if (start/r == end/r) {
        for (int i=start; i<=end; i++) {
            if (ans > a[i]) {
                ans = a[i];
            }
        }
        return ans;
    }
    while (true) {
        if (ans > a[start]) {
            ans = a[start];
        }
        start += 1;
        if (start % r == 0) {
            break;
        }
    }
    while (true) {
        if (ans > a[end]) {
            ans = a[end];
        }
        end -= 1;
        if (end % r == r-1) {
            break;
        }
    }
    int start_group = start/r;
    int end_group = end/r;
    for (int i=start_group; i<=end_group; i++) {
        if (ans > d[i]) {
            ans = d[i];
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    int r = (int)sqrt(n);
    int g = n / r;
    if (n % r != 0) g += 1;
    vector<int> d(g);
    for (int i=0; i<n; i++) {
        if (i % r == 0) {
            d[i/r] = a[i];
        } else {
            if (d[i/r] > a[i]) {
                d[i/r] = a[i];
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i, v;
            cin >> i >> v;
            update(a, d, r, i-1, v);
        } else {
            int i, j;
            cin >> i >> j;
            cout << query(a, d, r, i-1, j-1) << '\n';
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;
public class Main {
    static void update(int[] a, int[] d, int r, int index, int v) {
        a[index] = v;
        int group = index / r;
        int start = group * r;
        int end = start + r;
        if (end > a.length) end = a.length;
        d[group] = a[start];
        for (int i=start; i<end; i++) {
            if (d[group] > a[i]) {
                d[group] = a[i];
            }
        }
    }
    static int query(int[] a, int[] d, int r, int start, int end) {
        int n = a.length;
        int ans = a[start];
        if (start/r == end/r) {
            for (int i=start; i<=end; i++) {
                if (ans > a[i]) {
                    ans = a[i];
                }
            }
            return ans;
        }
        while (true) {
            if (ans > a[start]) {
                ans = a[start];
            }
            start += 1;
            if (start % r == 0) {
                break;
            }
        }
        while (true) {
            if (ans > a[end]) {
                ans = a[end];
            }
            end -= 1;
            if (end % r == r-1) {
                break;
            }
        }
        int start_group = start/r;
        int end_group = end/r;
        for (int i=start_group; i<=end_group; i++) {
            if (ans > d[i]) {
                ans = d[i];
            }
        }
        return ans;
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i=0; i<n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        int r = (int)Math.floor(Math.sqrt(n));
        int g = n / r;
        if (n % r != 0) g += 1;
        int[] d = new int[g];
        for (int i=0; i<n; i++) {
            if (i % r == 0) {
                d[i/r] = a[i];
            } else {
                if (d[i/r] > a[i]) {
                    d[i/r] = a[i];
                }
            }
        }
        int q = Integer.parseInt(br.readLine());
        while (q-- > 0) {
            line = br.readLine().split(" "); 
            int what = Integer.parseInt(line[0]);
            if (what == 1) {
                int i = Integer.parseInt(line[1]);
                int v = Integer.parseInt(line[2]);
                update(a, d, r, i-1, v);
            } else {
                int i = Integer.parseInt(line[1]);
                int j = Integer.parseInt(line[2]);
                bw.write(query(a, d, r, i-1, j-1)+"\n");
            }
        }
        bw.flush();
    }
}

import sys
import math
input = sys.stdin.readline

def update(a, d, r, index, v):
    a[index] = v
    group = index // r
    start = group * r
    end = start + r
    if end > len(a):
        end = len(a)
    d[group] = a[start]
    for i in range(start, end):
        if d[group] > a[i]:
            d[group] = a[i]

def query(a, d, r, start, end):
    n = len(a)
    ans = a[start]
    if start // r == end // r:
        for i in range(start, end+1):
            if ans > a[i]:
                ans = a[i]
        return ans
    
    while True:
        if ans > a[start]:
            ans = a[start]
        start += 1
        if start % r == 0:
            break

    while True:
        if ans > a[end]:
            ans = a[end]
        end -= 1
        if end % r == r-1:
            break
            
    start_group = start // r
    end_group = end // r
    for i in range(start_group, end_group+1):
        if ans > d[i]:
            ans = d[i]

    return ans

n = int(input())
a = list(map(int, input().split()))
r = (int)(n ** 0.5)
g = n // r
if n % r != 0:
    g += 1
d = [0] * g
for i in range(n):
    if i % r == 0:
        d[i//r] = a[i]
    else:
        if d[i//r] > a[i]:
            d[i//r] = a[i]

q = int(input())
for _ in range(q):
    t, t1, t2 = map(int, input().split())
    if t == 1:
        i, v = t1, t2
        update(a, d, r, i-1, v)
    else:
        i, j = t1, t2
        print(query(a, d, r, i-1, j-1))

최솟값 대신 합을 구하는 문제입니다. 소스 6으로 해결할 수 있습니다.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
void update(vector<long long> &a, vector<long long> &d, int r, int index, long long v) {
    int group = index / r;
    d[group] = d[group] - a[index] + v;
    a[index] = v;
}
long long query(vector<long long> &a, vector<long long> &d, int r, int start, int end) {
    int n = a.size();
    long long ans = 0;
    if (start/r == end/r) {
        for (int i=start; i<=end; i++) {
            ans += a[i];
        }
        return ans;
    }
    while (true) {
        ans += a[start];
        start += 1;
        if (start % r == 0) {
            break;
        }
    }
    while (true) {
        ans += a[end];
        end -= 1;
        if (end % r == r-1) {
            break;
        }
    }
    int start_group = start/r;
    int end_group = end/r;
    for (int i=start_group; i<=end_group; i++) {
        ans += d[i];
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    int r = (int)sqrt(n);
    int g = n / r;
    if (n % r != 0) g += 1;
    vector<long long> d(g);
    for (int i=0; i<n; i++) {
        d[i/r] += a[i];
    }
    int q = m + k;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            long long v;
            cin >> i >> v;
            update(a, d, r, i-1, v);
        } else {
            int i, j;
            cin >> i >> j;
            cout << query(a, d, r, i-1, j-1) << '\n';
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;
public class Main {
    static void update(long[] a, long[] d, int r, int index, long v) {
        int group = index / r;
        d[group] = d[group] - a[index] + v;
        a[index] = v;
    }
    static long query(long[] a, long[] d, int r, int start, int end) {
        int n = a.length;
        long ans = 0;
        if (start/r == end/r) {
            for (int i=start; i<=end; i++) {
                ans += a[i];
            }
            return ans;
        }
        while (true) {
            ans += a[start];
            start += 1;
            if (start % r == 0) {
                break;
            }
        }
        while (true) {
            ans += a[end];
            end -= 1;
            if (end % r == r-1) {
                break;
            }
        }
        int start_group = start/r;
        int end_group = end/r;
        for (int i=start_group; i<=end_group; i++) {
            ans += d[i];
        }
        return ans;
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int k = Integer.parseInt(line[2]);
        long[] a = new long[n];
        for (int i=0; i<n; i++) {
            a[i] = Long.parseLong(br.readLine());
        }
        int r = (int)Math.floor(Math.sqrt(n));
        int g = n / r;
        if (n % r != 0) g += 1;
        long[] d = new long[g];
        for (int i=0; i<n; i++) {
            d[i/r] += a[i];
        }
        int q = m + k;
        while (q-- > 0) {
            line = br.readLine().split(" "); 
            int what = Integer.parseInt(line[0]);
            if (what == 1) {
                int i = Integer.parseInt(line[1]);
                long v = Long.parseLong(line[2]);
                update(a, d, r, i-1, v);
            } else {
                int i = Integer.parseInt(line[1]);
                int j = Integer.parseInt(line[2]);
                bw.write(query(a, d, r, i-1, j-1)+"\n");
            }
        }
        bw.flush();
    }
}

import sys
import math
input = sys.stdin.readline

def update(a, d, r, index, v):
    group = index // r
    d[group] = d[group] - a[index] + v
    a[index] = v

def query(a, d, r, start, end):
    n = len(a)
    ans = 0
    if start // r == end // r:
        for i in range(start, end+1):
            ans += a[i]
        return ans
    
    while True:
        ans += a[start]
        start += 1
        if start % r == 0:
            break

    while True:
        ans += a[end]
        end -= 1
        if end % r == r-1:
            break
            
    start_group = start // r
    end_group = end // r
    for i in range(start_group, end_group+1):
        ans += d[i]

    return ans

n, m, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
r = (int)(n ** 0.5)
g = n // r
if n % r != 0:
    g += 1
d = [0] * g
for i in range(n):
    d[i//r] += a[i]

q = m + k
for _ in range(q):
    t, t1, t2 = map(int, input().split())
    if t == 1:
        i, v = t1, t2
        update(a, d, r, i-1, v)
    else:
        i, j = t1, t2
        print(query(a, d, r, i-1, j-1))

최솟값과 다르게 합은 뺄셈을 이용할 수 있기 때문에 update의 구현이 간단해집니다.

제곱근 분할법을 사용해서 해결할 수 있는 문제의 일부는 세그먼트 트리로 해결할 수 있습니다. 세그먼트 트리의 변경, 쿼리의 시간 복잡도는 $O(\lg{ N })$으로 제곱근 분할법보다 훨씬 빠릅니다. 세그먼트 트리를 사용하는 것이 훨씬 좋습니다.

제곱근 분할법은 모스 알고리즘의 기본 아이디어가 되는 알고리즘입니다. 모스 알고리즘을 구현할 때 이외에는 구현할 일이 많지 않습니다.