Dynamic Segment Tree: 지연 노드 생성

Dynamic Segtree, Dynamic Segment Tree, 동적 세그

정의

Dynamic Segment Tree 는 값 범위가 매우 크지만 실제 접근 위치가 희소할 때, 필요한 노드만 생성 하는 세그먼트 트리입니다.

공간: O(Q log V), Q = 쿼리 수, V = 값 범위

구조

포인터 기반, 또는 map<int, int> 로 자식 인덱스 관리.

struct Node { long long sum = 0; Node *l = nullptr, *r = nullptr; };

void update(Node*& n, long long lo, long long hi, long long pos, long long v) {
    if (!n) n = new Node();
    if (lo == hi) { n->sum += v; return; }
    long long mid = (lo + hi) / 2;
    if (pos <= mid) update(n->l, lo, mid, pos, v);
    else update(n->r, mid + 1, hi, pos, v);
    n->sum = (n->l ? n->l->sum : 0) + (n->r ? n->r->sum : 0);
}

대안

• 좌표 압축 + 일반 Segment Tree: 오프라인 처리 가능하면 대개 더 간단
• Persistent Segtree: 버전 추적 필요 시

참고

• Segment Tree
• Persistent Segtree