2차원 세그먼트 트리 – 학습

1강 평면 질의를 위한 트리의 트리 공식

문제

2차원 격자에서 점 갱신과 직사각형 질의(합/최대/최소)를 빠르게 처리한다. 1차원 세그먼트 트리가 $O(\log n)$ 이듯, 2차원에서는 두 축 모두에 세그먼트 트리를 세워 $O(\log^2)$ 을 노린다.

트리의 트리 구조

바깥 트리는 $$x$$ 축을 구간 분할한다. 바깥 트리의 각 노드는 그 $$x$$ 구간에 속한 점들로 만든 안쪽 $$y$$ 축 세그먼트 트리를 가진다. 직사각형 $[x_1,x_2]\times[y_1,y_2]$ 질의는:

바깥 트리에서 $$[x_1,x_2]$$ 를 덮는 $O(\log n)$ 개 노드를 고른다.
각 노드의 안쪽 트리에서 $$[y_1,y_2]$$ 합을 $O(\log m)$ 에 구한다.

총 $O(\log n\log m)$ .

점 갱신

점 $$(x,y)$$ 를 갱신하면 바깥 트리에서 $$x$$ 를 포함하는 루트→리프 경로의 $O(\log n)$ 개 노드 각각에서, 그 안쪽 트리의 $$y$$ 위치를 $O(\log m)$ 에 갱신한다. 총 $O(\log n\log m)$ .

메모리: 빽빽함 vs 동적

격자가 $N\times M$ 으로 작으면 안쪽 트리를 배열로 통째 잡아 $$O(NM)$$ 메모리. 좌표가 크고 점이 희소하면:

동적(포인터) 안쪽 트리: 안쪽 노드를 필요할 때만 생성. 점 $$Q$$ 개면 메모리 $O(Q\log n\log m)$ .
좌표 압축 + 머지소트 트리: 정적 질의면 각 바깥 노드에 정렬된 $$y$$ 리스트를 두는 변형도 있다.

다른 접근과 비교

방법	갱신	질의	비고
2D BIT	$O(\log n\log m)$	$O(\log n\log m)$	합 전용, 구현 짧음
2D 세그트리	$O(\log n\log m)$	$O(\log n\log m)$	min/max 등 일반 결합
오프라인 + 정렬 + 1D BIT	$O(\log)$	—	점 갱신·정적이면 가장 빠름

합만 필요하면 2D 펜윅이 더 짧다. min/max처럼 역원이 없는 결합이나 구간 갱신이 필요하면 2D 세그먼트 트리가 답이다.

주의

2D 세그트리에서 구간(직사각형) 갱신 + 직사각형 질의 를 동시에 lazy로 지원하는 것은 매우 까다롭다. 일반적으로 점 갱신/직사각형 질의 또는 직사각형 갱신/점 질의 중 하나로 설계한다.

2강 2D 세그먼트 트리 구현과 활용 공식

정적 격자 구현 (합, 점 갱신·직사각형 질의)

바깥 $$x$$ 트리의 각 노드가 안쪽 $$y$$ 트리(배열)를 가진다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, M;
vector<vector<ll>> seg;     // seg[xnode][ynode]

// 안쪽 y 트리 점 갱신
void updateY(int xnode, int ynode, int yl, int yr, int y, ll val) {
    if (yl == yr) { seg[xnode][ynode] = val; return; }
    int ym = (yl + yr) / 2;
    if (y <= ym) updateY(xnode, ynode * 2, yl, ym, y, val);
    else         updateY(xnode, ynode * 2 + 1, ym + 1, yr, y, val);
    seg[xnode][ynode] = seg[xnode][ynode * 2] + seg[xnode][ynode * 2 + 1];
}
// 바깥 x 트리 점 갱신: x 경로의 모든 노드에서 y 갱신
void updateX(int xnode, int xl, int xr, int x, int y, ll val) {
    if (xl != xr) {
        int xm = (xl + xr) / 2;
        if (x <= xm) updateX(xnode * 2, xl, xm, x, y, val);
        else         updateX(xnode * 2 + 1, xm + 1, xr, x, y, val);
    }
    // 이 x노드의 y트리에 점 (.,y) 갱신
    // 합 모델: 리프에서 부분합이 필요하면 값 누적; 여기선 단순 set 예시
    updateY(xnode, 1, 1, M, y, val);
}
// 안쪽 y 질의
ll queryY(int xnode, int ynode, int yl, int yr, int y1, int y2) {
    if (y2 < yl || yr < y1) return 0;
    if (y1 <= yl && yr <= y2) return seg[xnode][ynode];
    int ym = (yl + yr) / 2;
    return queryY(xnode, ynode * 2, yl, ym, y1, y2)
         + queryY(xnode, ynode * 2 + 1, ym + 1, yr, y1, y2);
}
// 바깥 x 질의
ll queryX(int xnode, int xl, int xr, int x1, int x2, int y1, int y2) {
    if (x2 < xl || xr < x1) return 0;
    if (x1 <= xl && xr <= x2) return queryY(xnode, 1, 1, M, y1, y2);
    int xm = (xl + xr) / 2;
    return queryX(xnode * 2, xl, xm, x1, x2, y1, y2)
         + queryX(xnode * 2 + 1, xm + 1, xr, x1, x2, y1, y2);
}

자주 하는 실수

메모리 폭발. 정적 풀배열은 바깥 $$O(N)$$ × 안쪽 $$O(M)$$ = $$O(NM)$$ . $$N,M$$ 이 크면 동적 노드나 좌표 압축이 필수.
합 모델에서 점 갱신. "set"이 아니라 "add"가 필요하면 안쪽 트리도 누적합으로 다뤄야 한다. 위 예시는 set 모델이니 모델을 맞춘다.
min/max 결합 시 항등원. 합은 0, min은 $+\infty$ , max는 $-\infty$ 로 빈 구간 반환값을 바꿔야 한다.
인덱스 1-base/0-base 혼용. 두 축 모두 일관되게.

응용

문제	모델
동적 2D 부분합	합, 점 갱신·사각 질의
평면 위 최대값 질의	max 결합
K-D 점 카운팅(온라인)	동적/압축 2D 세그

동적 변형 메모

희소한 큰 좌표는 바깥 트리는 그대로 두되 안쪽 $$y$$ 트리를 동적 세그먼트 트리(포인터) 로 바꾼다. 메모리는 점 개수 × $\log n\log m$ . 좌표를 미리 모아 압축할 수 있으면 압축 후 정적 배열이 캐시 효율상 더 빠르다.