다차원 세그먼트 트리 (Multi-dimensional Segment Tree)

정의

다차원 세그먼트 트리 (Multi-dimensional Segment Tree) 는 2차원 이상 배열에서 직사각형 구간 쿼리 + 점 갱신 을 O(log^d N) 에 처리하는 자료구조 (d = 차원). 1차원 세그먼트 트리를 재귀적으로 확장.

대표 변형:

• 2D Segment Tree: 행/열 각각 세그트리 중첩. 메모리 O(N × M), 쿼리 O(log N × log M).
• Persistent Segment Tree (PST): 버전별 복사, PST 참고. 2D offline 쿼리로 응용 가능.
• Offline 2D Segment Tree: 좌표 압축 + 쿼리 정렬, 메모리 O(Q log N).

문제 상황과 동기

N × M 격자, Q개 쿼리: “직사각형 (r1, c1, r2, c2) 내 합/min/max” + 점 (r, c) 갱신.

• naive: 매 쿼리마다 직사각형 순회 O(NM). Q=10^4, NM=10^6 면 10^10, TLE.
• 2D prefix sum: 쿼리 O(1), 갱신 O(NM) 재계산. 갱신 빈번하면 불가.
• 2D Segment Tree: 쿼리 O(log N × log M), 갱신 O(log N × log M), 메모리 O(4NM).
• Offline 2D (PST 응용): 좌표 압축 + 정렬, 메모리 O(Q log N), 온라인 불가.

핵심 통찰: 1차원 세그트리의 각 노드가 다시 세그트리를 갖는다. 중첩 구조로 차원 확장.

시각화

핵심 아이디어

1. 2D Segment Tree

행 세그트리 × 열 세그트리 중첩.

• 외부 트리: 행 [l, r] 분할.
• 각 노드 내부: 열 [c1, c2] 분할하는 내부 세그트리.

구조:

외부 노드 [0, N-1]
  ├─ 내부 트리 (열 세그트리) [0, M-1]
  ├─ 왼쪽 자식 [0, mid]
  └─ 오른쪽 자식 [mid+1, N-1]

메모리: 외부 4N × 내부 4M = O(16NM).

쿼리:

1. 외부 트리에서 행 [r1, r2] 분할.
2. 각 해당 노드의 내부 트리에서 열 [c1, c2] 쿼리.
3. 결과 병합 (합/min/max).

복잡도: O(log N × log M).

2. Persistent Segment Tree (PST) 응용

1차원 PST 는 버전별 배열 유지. 2D 로 확장:

• 각 행마다 1차원 PST 를 만들고, 행 축도 PST 로 관리.
• 쿼리 (r1, c1, r2, c2) = PST[r2] - PST[r1-1] 의 구간 [c1, c2].

주로 “k번째 수” 문제에 사용. 예: 직사각형 내 k번째 작은 값.

3. Offline 2D Segment Tree

쿼리를 미리 받아 좌표 압축 + 정렬 후 스위핑.

• 한 축 (보통 x) 으로 정렬.
• y 축은 동적 세그트리 (좌표 압축).
• 메모리 O(Q log N), 쿼리당 O(log^2 N).

온라인 불가, 하지만 메모리 절약.

알고리즘

2D Segment Tree (중첩)

build_2d(node, r1, r2):
    if r1 == r2:
        node.inner_tree = build_1d(grid[r1])
    else:
        mid = (r1 + r2) / 2
        build_2d(node.left, r1, mid)
        build_2d(node.right, mid+1, r2)
        node.inner_tree = merge(node.left.inner_tree, node.right.inner_tree)

query_2d(node, r1, r2, qr1, qr2, qc1, qc2):
    if [r1, r2] ∩ [qr1, qr2] = ∅:
        return neutral
    if [r1, r2] ⊆ [qr1, qr2]:
        return query_1d(node.inner_tree, qc1, qc2)
    mid = (r1 + r2) / 2
    left_val = query_2d(node.left, r1, mid, qr1, qr2, qc1, qc2)
    right_val = query_2d(node.right, mid+1, r2, qr1, qr2, qc1, qc2)
    return merge(left_val, right_val)

update_2d(node, r1, r2, qr, qc, val):
    update_1d(node.inner_tree, qc, val)
    if r1 == r2:
        return
    mid = (r1 + r2) / 2
    if qr <= mid:
        update_2d(node.left, r1, mid, qr, qc, val)
    else:
        update_2d(node.right, mid+1, r2, qr, qc, val)
    node.inner_tree = merge(node.left.inner_tree, node.right.inner_tree)

Offline 2D (스위핑 + 동적 세그트리)

compress(coords):
    sorted_unique = sort(set(coords))
    return map {coord -> index}

offline_2d(queries):
    compress x and y coords
    sort queries by x (or sweep axis)
    for each x:
        for each query at x:
            dynamic_segtree.update(y, val)
        for each rect query at x:
            result = dynamic_segtree.query(y1, y2)

구현

2D 세그트리 구현 (합 쿼리, 점 갱신).

// 2D Segment Tree: 직사각형 합 쿼리 + 점 갱신
#include <bits/stdc++.h>
using namespace std;
​
struct Segtree1D {
  vector<long long> tree;
  int n;
  Segtree1D(int sz) : n(sz), tree(4*sz, 0) {}
  void update(int node, int l, int r, int pos, long long val) {
      if (l == r) { tree[node] = val; return; }
      int mid = (l + r) / 2;
      if (pos <= mid) update(2*node, l, mid, pos, val);
      else update(2*node+1, mid+1, r, pos, val);
      tree[node] = tree[2*node] + tree[2*node+1];
  }
  long long query(int node, int l, int r, int ql, int qr) {
      if (qr < l || r < ql) return 0;
      if (ql <= l && r <= qr) return tree[node];
      int mid = (l + r) / 2;
      return query(2*node, l, mid, ql, qr) + query(2*node+1, mid+1, r, ql, qr);
  }
};
​
struct Segtree2D {
  vector<Segtree1D> outer;
  int n, m;
  Segtree2D(int rows, int cols) : n(rows), m(cols), outer(4*rows, Segtree1D(cols)) {}
  void update_outer(int node, int l, int r, int row, int col, long long val) {
      outer[node].update(1, 0, m-1, col, val);
      if (l == r) return;
      int mid = (l + r) / 2;
      if (row <= mid) update_outer(2*node, l, mid, row, col, val);
      else update_outer(2*node+1, mid+1, r, row, col, val);
      long long left_val = outer[2*node].query(1, 0, m-1, col, col);
      long long right_val = outer[2*node+1].query(1, 0, m-1, col, col);
      outer[node].update(1, 0, m-1, col, left_val + right_val);
  }
  long long query_outer(int node, int l, int r, int qr1, int qr2, int qc1, int qc2) {
      if (qr2 < l || r < qr1) return 0;
      if (qr1 <= l && r <= qr2) return outer[node].query(1, 0, m-1, qc1, qc2);
      int mid = (l + r) / 2;
      return query_outer(2*node, l, mid, qr1, qr2, qc1, qc2)
           + query_outer(2*node+1, mid+1, r, qr1, qr2, qc1, qc2);
  }
  void update(int r, int c, long long val) { update_outer(1, 0, n-1, r, c, val); }
  long long query(int r1, int c1, int r2, int c2) { return query_outer(1, 0, n-1, r1, r2, c1, c2); }
};
​
int main() {
  int n, m, q; cin >> n >> m >> q;
  Segtree2D seg(n, m);
  while (q--) {
      int t; cin >> t;
      if (t == 1) {
          int r, c; long long v; cin >> r >> c >> v;
          seg.update(r, c, v);
      } else {
          int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
          cout << seg.query(r1, c1, r2, c2) << "\n";
      }
  }
}

# 2D Segment Tree (간략화, 실전은 C++ 권장)
# 메모리/속도 이슈로 Python 은 보통 2D fenwick 또는 sparse table 선호
import sys
input = sys.stdin.readline
​
class Segtree1D:
  def __init__(self, sz):
      self.n = sz
      self.tree = [0] * (4 * sz)
  
  def update(self, node, l, r, pos, val):
      if l == r:
          self.tree[node] = val
          return
      mid = (l + r) // 2
      if pos <= mid:
          self.update(2*node, l, mid, pos, val)
      else:
          self.update(2*node+1, mid+1, r, pos, val)
      self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
  
  def query(self, node, l, r, ql, qr):
      if qr < l or r < ql:
          return 0
      if ql <= l <= r <= qr:
          return self.tree[node]
      mid = (l + r) // 2
      return self.query(2*node, l, mid, ql, qr) + self.query(2*node+1, mid+1, r, ql, qr)
​
# Segtree2D 는 재귀 깊이 + 메모리 문제로 Python 비추천
# 실전: 좌표 압축 + offline 또는 2D fenwick
​
n, m, q = map(int, input().split())
# 단순 2D 배열로 대체 (교육용)
grid = [[0]*m for _ in range(n)]
​
for _ in range(q):
  line = list(map(int, input().split()))
  if line[0] == 1:
      r, c, v = line[1], line[2], line[3]
      grid[r][c] = v
  else:
      r1, c1, r2, c2 = line[1], line[2], line[3], line[4]
      total = sum(grid[i][j] for i in range(r1, r2+1) for j in range(c1, c2+1))
      print(total)

3 3 5
1 0 0 5
1 1 1 3
1 2 2 7
2 0 0 2 2
2 1 1 1 1

15
3

복잡도

3D 이상: O(log^d N) 쿼리, 메모리 O(N^d). d ≥ 3 은 실전 거의 없음. 좌표 압축 필수.

변형

1. 2D Fenwick Tree

2차원 누적 합, 역원 있는 연산 (합, XOR) 만 가능. 메모리 O(NM), 구현 간단.

struct Fenwick2D {
    vector<vector<long long>> tree;
    int n, m;
    Fenwick2D(int r, int c) : n(r), m(c), tree(r+1, vector<long long>(c+1, 0)) {}
    void add(int r, int c, long long v) {
        for (int i = r; i <= n; i += i & -i)
            for (int j = c; j <= m; j += j & -j)
                tree[i][j] += v;
    }
    long long sum(int r, int c) {
        long long res = 0;
        for (int i = r; i > 0; i -= i & -i)
            for (int j = c; j > 0; j -= j & -j)
                res += tree[i][j];
        return res;
    }
    long long rect_sum(int r1, int c1, int r2, int c2) {
        return sum(r2, c2) - sum(r1-1, c2) - sum(r2, c1-1) + sum(r1-1, c1-1);
    }
};

2. Persistent Segment Tree for 2D

PST 를 y축으로 만들고, x 축마다 새 버전 생성. “직사각형 내 k번째 수” 쿼리 O(log^2 N).

메모리: O(N log N + Q log N).

3. Fractional Cascading

2D 범위 쿼리 최적화, 이론상 O(log N + K) (K = 결과 개수). 구현 복잡, 실전 희귀.

함정

1. 메모리 폭발

N=M=1000 이면 2D 세그트리는 16 × 10^6 int = 64MB. N=10^4 이면 6.4GB. 좌표 압축 필수.

2. 재귀 깊이

Python 은 재귀 한도 (기본 1000) 로 세그트리 깊이 제약. sys.setrecursionlimit(10**6) 또는 iterative 구현.

3. Offline vs Online

Offline 은 쿼리 순서 바뀜. 온라인 필수 조건 확인.

4. 좌표 1-indexed vs 0-indexed

세그트리 내부 로직과 문제 입력 좌표 혼동. 일관성 유지.

5. Lazy Propagation 2D

구간 갱신까지 하려면 lazy propagation 이 외부/내부 트리 둘 다 필요. 구현 난이도 극상. 실전에서는 offline 또는 다른 자료구조 고려.

BOJ 연습 문제

참고

• 세그먼트 트리
• 퍼시스턴트 세그먼트 트리
• 펜윅 트리
• 희소 배열