# Dynamic Segment Tree

Dynamic Segment Tree는 좌표 범위가 매우 크지만 실제로 접근하는 지점이나 구간이 적을 때 필요한 node만 만드는 Segment Tree입니다. 좌표 압축이 어렵거나 온라인으로 새로운 좌표가 계속 등장하는 문제에서 유용합니다.

## 문제 신호

| 문제 표현 | Dynamic Segment Tree 관점 |
| --- | --- |
| 좌표가 `10^9` 또는 `10^18`까지 크다 | array tree 불가 |
| 업데이트/질의 수는 상대적으로 작다 | touched node만 생성 |
| 온라인으로 좌표가 들어온다 | 사전 좌표 압축 어려움 |
| 구간 update와 구간 sum/min query | lazy node 필요 |
| 대부분 구간은 기본값 0이다 | sparse structure |

좌표를 모두 미리 알고 있고 정렬해도 의미가 보존된다면 좌표 압축이 더 단순합니다. Dynamic Segment Tree는 압축이 불편하거나 구간 전체 길이가 의미 있을 때 선택합니다.

## 기본 구조

![\[0,8)에서\[5,6)에3을 더하면\[0,8),\[4,8),\[4,6),\[5,6) 네 노드만 생성됩니다. 다른 자식은0입니다.](lesson-assets/structure-trace.svg)

[그림 크게 보기](https://git.readiz.com/h-contest-lesson/lessons/dynamic-segment-tree/lesson-assets/structure-trace.svg)

점 하나의 갱신에서는 그 점으로 내려가는 경로만 만듭니다. 그림은 초기값이 0이고 기존 lazy가 없는 경우입니다. 구간 갱신 뒤 lazy를 내리는 질의에서는 양쪽 자식이 새로 생길 수 있습니다.

일반 Segment Tree는 `4N` 배열을 잡지만, Dynamic Segment Tree는 node pool을 두고 child index를 필요할 때 만듭니다.

```text
node {
  left child index
  right child index
  aggregate
  lazy
}
```

아래 구현의 모든 구간은 정수 좌표의 half-open `[left, right)`입니다. 루트는 `left < right`, 질의와 갱신은 루트 내부의 `left <= right` 범위입니다. 중간점은 `left + (right - left) / 2`로 계산하며, 구간 길이와 `길이 × 증가량`이 `long long` 범위에 들어와야 합니다.

## Range Add / Range Sum 구현

아래 구현은 모든 원소의 초기값이 0인 구간에 덧셈과 합 질의를 처리합니다. 생성하지 않은 자식의 합도 0으로 봅니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <vector>
using namespace std;

struct DynamicSegmentTree {
    struct Node {
        int leftChild = 0;
        int rightChild = 0;
        long long sum = 0;
        long long lazy = 0;
    };

    vector<Node> tree;
    long long rootLeft;
    long long rootRight;

    DynamicSegmentTree(long long left, long long right) : rootLeft(left), rootRight(right) {
        tree.push_back(Node());
        tree.push_back(Node());
    }

    int newNode() {
        tree.push_back(Node());
        return (int)tree.size() - 1;
    }

    void apply(int node, long long left, long long right, long long value) {
        tree[node].sum += (right - left) * value;
        tree[node].lazy += value;
    }

    void push(int node, long long left, long long right) {
        if (tree[node].lazy == 0 || right - left <= 1) {
            return;
        }
        long long mid = left + (right - left) / 2;
        if (tree[node].leftChild == 0) {
            tree[node].leftChild = newNode();
        }
        if (tree[node].rightChild == 0) {
            tree[node].rightChild = newNode();
        }
        long long value = tree[node].lazy;
        apply(tree[node].leftChild, left, mid, value);
        apply(tree[node].rightChild, mid, right, value);
        tree[node].lazy = 0;
    }

    long long childSum(int child) const {
        return child == 0 ? 0 : tree[child].sum;
    }

    void pull(int node) {
        tree[node].sum = childSum(tree[node].leftChild) + childSum(tree[node].rightChild);
    }

    void rangeAdd(int node, long long left, long long right, long long ql, long long qr, long long value) {
        if (qr <= left || right <= ql) {
            return;
        }
        if (ql <= left && right <= qr) {
            apply(node, left, right, value);
            return;
        }
        push(node, left, right);
        long long mid = left + (right - left) / 2;
        if (ql < mid) {
            if (tree[node].leftChild == 0) {
                tree[node].leftChild = newNode();
            }
            rangeAdd(tree[node].leftChild, left, mid, ql, qr, value);
        }
        if (mid < qr) {
            if (tree[node].rightChild == 0) {
                tree[node].rightChild = newNode();
            }
            rangeAdd(tree[node].rightChild, mid, right, ql, qr, value);
        }
        pull(node);
    }

    long long rangeSum(int node, long long left, long long right, long long ql, long long qr) {
        if (node == 0 || qr <= left || right <= ql) {
            return 0;
        }
        if (ql <= left && right <= qr) {
            return tree[node].sum;
        }
        push(node, left, right);
        long long mid = left + (right - left) / 2;
        return rangeSum(tree[node].leftChild, left, mid, ql, qr)
             + rangeSum(tree[node].rightChild, mid, right, ql, qr);
    }

    void add(long long left, long long right, long long value) {
        rangeAdd(1, rootLeft, rootRight, left, right, value);
    }

    long long sum(long long left, long long right) {
        return rangeSum(1, rootLeft, rootRight, left, right);
    }
};
```

루트 범위는 문제 조건보다 한 칸 넓은 half-open 범위로 잡습니다. 예를 들어 좌표가 `0 <= x <= 1e9`이면 `[0, 1000000001)`처럼 둡니다.

## 좌표 압축과 비교

| 조건 | 좌표 압축 | Dynamic Segment Tree |
| --- | --- | --- |
| 모든 좌표를 미리 알 수 있음 | 좋음 | 가능하지만 과함 |
| 구간 길이가 답에 직접 영향 | endpoint 보강 필요 | 자연스러움 |
| 온라인 좌표 등장 | 어려움 | 좋음 |
| 메모리 예측 | `O(K)` | `O(Q log C)` |
| 구현 난도 | 낮음 | 중간 |

좌표 압축에서는 구간 길이를 잃기 쉽습니다. 구간 합집합 길이처럼 실제 좌표 간격이 중요하면 compression interval을 별도로 관리해야 합니다.

## 메모리 계산

구간 update 하나가 깊이 `log C`만큼 node를 만들고, segment tree interval decomposition 때문에 여러 경로에 닿을 수 있습니다.

```text
node count = O(number_of_operations * log coordinate_range)
```

좌표 범위가 `2^60`이어도 깊이는 60입니다. 위 구현은 질의에서도 `push`가 자식을 만들 수 있으므로, 메모리를 계산할 때 업데이트와 질의 수를 모두 포함합니다.

## 시간 복잡도

| 작업 | 복잡도 |
| --- | --- |
| point update/query | `O(log C)` |
| range update/query | `O(log C)` |
| 생성 node 수 | touched interval 수에 비례 |
| 전체 메모리 | 보통 `O(Q log C)` |

## 로컬 연습: 큰 좌표의 구간 덧셈과 합

정수 좌표 0..10^12-1의 값은 처음에 모두 0입니다. A l r delta는 [l,r)에 delta를 더하고, S l r은 그 구간의 합을 묻습니다.

**입력:** Q 뒤 Q개 연산. 0 <= Q <= 20000, 0 <= l <= r <= 10^12, |delta| <= 100입니다. 합과 lazy는 long long으로 계산합니다.

**출력:** S 연산마다 합을 출력합니다.

### 예시

```text exercise=dynamic-segment-tree role=input
6
A 0 10 2
S 0 1
A 5 8 -1
S 4 9
S 9 10
S 5 5
```

```text exercise=dynamic-segment-tree role=output
2
7
2
0
```

**확인 방법:** 좌표 상한을 20으로 줄이면 실제 배열의 원소별 갱신·합산과 비교할 수 있습니다. 빈 구간, 전체 구간 갱신 뒤 작은 부분 질의, 같은 구간의 더하기·빼기를 검사합니다. 큰 상한에서는 10^12개의 배열을 만들지 말고 생성한 노드 수와 메모리를 함께 기록합니다.