제곱근 분할 (Sqrt Decomposition)

정의

제곱근 분할 (Sqrt Decomposition) 은 크기 N 배열을 √N 개씩 블록으로 나누고, 각 블록을 전처리해 구간 연산을 O(√N) 에 처리하는 자료구조 기법.

문제 상황과 동기

단일 원소 갱신과 구간 합 질의를 동시에 처리해야 한다.

• naive 갱신 O(1) + 쿼리 O(N): Q=10^5, N=10^5 면 O(NQ) 불가.
• prefix sum 쿼리 O(1) + 갱신 O(N): 갱신이 잦으면 재계산 오버헤드.
• seg tree: O(log N) 이지만 구현 복잡도 상승.
• sqrt decomposition: O(√N) 갱신 + O(√N) 쿼리. 구현은 seg tree 의 절반.

핵심 통찰: 블록 단위로 묶어 precompute 하면, partial 블록만 순회하고 full 블록은 블록 값으로 O(1) 처리.

시각화

핵심 아이디어

invariant: 블록 크기 B = √N. 각 블록의 합을 block_sum[k] 에 저장.

block_sum[k] = sum of a[k*B .. min((k+1)*B-1, N-1)]

range_add(l, r, x):
    for i in l..r:
        if i % B == 0 and i + B - 1 <= r:   # full block
            block_sum[i/B] += x * B
            i += B
        else:
            a[i] += x
            block_sum[i/B] += x

알고리즘

B = int(sqrt(N)) + 1
block_cnt = (N + B - 1) / B

// 전처리
for k in 0..block_cnt-1:
    block_sum[k] = sum of a[k*B .. min((k+1)*B-1, N-1)]

// 구간 합 쿼리
range_sum(l, r):
    res = 0
    while l <= r:
        if l % B == 0 and l + B - 1 <= r:
            res += block_sum[l / B]
            l += B
        else:
            res += a[l]
            l += 1
    return res

// 점 갱신
point_update(pos, val):
    block_sum[pos / B] += val - a[pos]
    a[pos] = val

구현

// Sqrt decomposition, range sum + point update
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  int n, q; cin >> n >> q;
  vector<long long> a(n);
  for (auto& v : a) cin >> v;
​
  int B = (int)sqrt(n) + 1;
  int bc = (n + B - 1) / B;
  vector<long long> block(bc, 0);
  for (int i = 0; i < n; i++) block[i / B] += a[i];
​
  while (q--) {
      int t; cin >> t;
      if (t == 1) {
          int l, r; cin >> l >> r; l--; r--;
          long long res = 0;
          while (l <= r) {
              if (l % B == 0 && l + B - 1 <= r) {
                  res += block[l / B];
                  l += B;
              } else {
                  res += a[l];
                  l++;
              }
          }
          cout << res << "\n";
      } else {
          int pos, val; cin >> pos >> val; pos--;
          block[pos / B] += val - a[pos];
          a[pos] = val;
      }
  }
}

import sys, math
input = sys.stdin.readline
n, q = map(int, input().split())
a = list(map(int, input().split()))
​
B = int(math.sqrt(n)) + 1
bc = (n + B - 1) // B
block = [0] * bc
for i in range(n):
  block[i // B] += a[i]
​
out = []
for _ in range(q):
  t, *rest = map(int, input().split())
  if t == 1:
      l, r = rest; l -= 1; r -= 1
      res = 0
      while l <= r:
          if l % B == 0 and l + B - 1 <= r:
              res += block[l // B]
              l += B
          else:
              res += a[l]
              l += 1
      out.append(str(res))
  else:
      pos, val = rest; pos -= 1
      block[pos // B] += val - a[pos]
      a[pos] = val
print("\n".join(out))

5 4
1 2 3 4 5
1 1 3
2 3 10
1 1 3
1 1 5

6
13
22

복잡도

변형 / 활용

함정

1. 블록 크기 조절

sqrt(N) + 1 을 더해 B 가 0 이 되지 않게. N=1 이면 B=2.

2. 경계 조건

마지막 블록이 B보다 짧을 수 있음. min((k+1)*B, N) 으로 범위 확인.

3. long long overflow

N=10^5, 값=10^9 면 block 합이 10^14 까지 가능. 64-bit 필요.

BOJ 연습 문제

참고

• Mo’s Algorithm
• 세그먼트 트리
• 펜윅 트리