# Persistent Lazy Segment Tree

Persistent Lazy Segment Tree는 구간 업데이트와 구간 질의를 처리하면서, 업데이트 이전 버전도 계속 보존하는 자료구조입니다. 일반 Persistent Segment Tree는 point update가 단순하지만, lazy propagation이 붙으면 clone 시점과 lazy 값 전달이 까다로워집니다.

## 문제 신호

| 문제 표현 | 접근 |
| --- | --- |
| 구간 업데이트 후 과거 버전 질의 | persistent lazy segment tree |
| version별 range sum/min query | version root 저장 |
| 업데이트가 많고 복사 비용을 줄여야 함 | path copying |
| 시간이 되돌아가는 쿼리 | persistence 또는 rollback |
| 좌표 범위가 매우 큼 | dynamic persistent tree 고려 |

과거 버전으로 되돌아가기만 하고 branching이 없으면 rollback lazy segment tree가 더 간단할 수 있습니다. 여러 version을 자유롭게 질의하면 persistence가 맞습니다.

## Clone 원칙

Persistence에서는 기존 node를 직접 바꾸면 안 됩니다. 값을 바꿀 node는 먼저 clone합니다.

```text
newNode = copy(oldNode)
modify(newNode)
return newNode
```

lazy propagation에서도 마찬가지입니다. `push`가 자식의 lazy 값을 바꾸는 순간 자식도 clone해야 합니다.

## Range Add, Range Sum 구현

아래 구현은 구간 add와 구간 sum을 처리합니다. 각 업데이트는 새 root index를 반환합니다.

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

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

struct PersistentLazySegmentTree {
    struct Node {
        long long sum = 0;
        long long lazy = 0;
        int left = -1;
        int right = -1;
    };

    int n;
    vector<Node> nodes;

    explicit PersistentLazySegmentTree(int n) : n(n) {
        // 필요한 노드는 build와 update에서 생성한다.
    }

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

    int newNode(const Node& node) {
        nodes.push_back(node);
        return (int)nodes.size() - 1;
    }

    int build(int left, int right, const vector<long long>& values) {
        int idx = newNode();
        if (right - left == 1) {
            nodes[idx].sum = values[left];
            return idx;
        }

        int mid = (left + right) / 2;
        nodes[idx].left = build(left, mid, values);
        nodes[idx].right = build(mid, right, values);
        pull(idx);
        return idx;
    }

    void pull(int idx) {
        nodes[idx].sum = nodes[nodes[idx].left].sum + nodes[nodes[idx].right].sum;
    }

    int cloneNode(int idx) {
        return newNode(nodes[idx]);
    }

    void apply(int idx, int left, int right, long long delta) {
        nodes[idx].sum += delta * (right - left);
        nodes[idx].lazy += delta;
    }

    void push(int idx, int left, int right) {
        if (nodes[idx].lazy == 0 || right - left == 1) {
            return;
        }

        int mid = (left + right) / 2;
        nodes[idx].left = cloneNode(nodes[idx].left);
        nodes[idx].right = cloneNode(nodes[idx].right);

        long long delta = nodes[idx].lazy;
        apply(nodes[idx].left, left, mid, delta);
        apply(nodes[idx].right, mid, right, delta);
        nodes[idx].lazy = 0;
    }

    int rangeAdd(int idx, int left, int right, int queryLeft, int queryRight, long long delta) {
        if (queryRight <= left || right <= queryLeft) {
            return idx;
        }

        int cur = cloneNode(idx);
        if (queryLeft <= left && right <= queryRight) {
            apply(cur, left, right, delta);
            return cur;
        }

        push(cur, left, right);
        int mid = (left + right) / 2;
        nodes[cur].left = rangeAdd(nodes[cur].left, left, mid, queryLeft, queryRight, delta);
        nodes[cur].right = rangeAdd(nodes[cur].right, mid, right, queryLeft, queryRight, delta);
        pull(cur);
        return cur;
    }

    long long rangeSum(int idx, int left, int right, int queryLeft, int queryRight, long long carry = 0) const {
        if (queryRight <= left || right <= queryLeft) {
            return 0;
        }
        if (queryLeft <= left && right <= queryRight) {
            return nodes[idx].sum + carry * (right - left);
        }

        carry += nodes[idx].lazy;
        int mid = (left + right) / 2;
        return rangeSum(nodes[idx].left, left, mid, queryLeft, queryRight, carry)
            + rangeSum(nodes[idx].right, mid, right, queryLeft, queryRight, carry);
    }
};
```

질의는 조상 lazy를 `carry`로 전달하므로 노드 생성이나 변경을 하지 않습니다. 완전히 포함된 구간은 저장 합에 조상 증가량만 더합니다. `build(0, n, values)`로 `n >= 1`인 초기 루트를 만들고, 각 갱신 반환 루트를 별도로 저장합니다. 구간은 `[0,n)` 내부의 반열린 구간이며 합·곱은 정수 범위 안이어야 합니다.

## 메모리 계산

구간 업데이트 하나는 방문한 경로와 필요한 lazy child clone을 만듭니다.

| 작업 | 새 node 수 |
| --- | ---: |
| point update | `O(log N)` |
| range update with lazy | `O(log N)` 중심, push clone 포함 |
| build | `O(N)` |

실제 상수는 일반 persistent tree보다 큽니다. `Q log N * 2~4` 정도의 node 수를 넉넉히 잡습니다.

## Rollback과 비교

| 방식 | 장점 | 제한 |
| --- | --- | --- |
| rollback | 구현 단순, 메모리 적음 | 최신 상태에서 되돌리기 중심 |
| persistence | 임의 version 질의 가능 | node clone과 메모리 관리 필요 |
| offline divide conquer | 특정 쿼리 구조에 강함 | 쿼리 재배치 필요 |

문제에서 version graph가 tree처럼 branching하면 persistence가 자연스럽습니다.

## 시간 복잡도

| 연산 | 시간 |
| --- | ---: |
| build | `O(N)` |
| range update | `O(log N)` |
| range query | `O(log N)` |
| version root 저장 | `O(1)` |

lazy propagation이 있어도 segment tree의 높이는 유지됩니다.