--- id: "lessons/segment-tree" title: "Segment Tree: 구간 합과 미룬 갱신" description: "점 대입에서 구간 덧셈까지, 노드의 합과 lazy 값을 함께 추적합니다." kind: "record" published: "2026-10-04T00:00:00.000Z" tags: ["알고리즘","C++","자료구조"] url: "https://www.readiz.com/records/segment-tree/" markdownUrl: "https://www.readiz.com/records/segment-tree/index.md" --- # Segment Tree: 구간 합과 미룬 갱신 [Fenwick Tree](https://www.readiz.com/records/fenwick-tree/)에서는 정해진 prefix 구간을 모아 합을 구했습니다. 이번에는 배열을 반씩 나눈 구간에서 답을 합칩니다. **점 하나를 새 값으로 바꾸는 연산**과 **구간 전체에 값을 더하는 연산**을 구분하고, 후자의 작업을 자식에게 미루는 과정을 따라갑니다. 배열 값이 바뀌는 동안 구간 합·최솟값·최댓값을 묻는다면, 구간을 반으로 나눈 트리에 결과를 저장할 수 있습니다. 바뀐 위치를 포함하는 구간만 고쳐 점 갱신과 구간 질의를 `O(log n)`에 처리합니다. ## 구간을 반으로 나누는 트리 Segment Tree의 각 노드는 배열의 한 구간을 담당합니다. ```text [0, 7] ├─ [0, 3] │ ├─ [0, 1] │ └─ [2, 3] └─ [4, 7] ├─ [4, 5] └─ [6, 7] ``` 루트는 전체 구간을 담당하고, 자식은 구간을 절반씩 나누어 담당합니다. 길이가 1인 구간이 leaf입니다. 구간 합 Segment Tree라면 각 노드는 자신이 담당하는 구간의 합을 저장합니다. ```text node [l, r] = a[l] + a[l + 1] + ... + a[r] ``` 구간 최솟값이면 합 대신 최솟값을 저장하면 됩니다. 중요한 점은 두 자식의 값을 합쳐 부모 값을 만들 수 있어야 한다는 것입니다. ## Fenwick과 구분해서 선택하기 점 덧셈과 구간 합만 필요하면 Fenwick의 짧은 구현으로 충분합니다. 구간 합을 두 prefix의 차로 만들 수 있기 때문입니다. 반면 일반적인 구간 최솟값은 두 prefix 최솟값을 빼서 얻을 수 없습니다. Segment Tree는 구간을 나누어 합·최솟값·최댓값 등 필요한 연산으로 합칩니다. 구간 덧셈과 구간 합도 두 Fenwick을 조합하면 처리할 수 있습니다. 여기서 Segment Tree를 배우는 목적은 **구간을 합치는 규칙과 갱신을 합성하는 규칙을 직접 정하는 것**입니다. lazy를 붙였다고 모든 업데이트를 자동으로 처리할 수 있는 것은 아닙니다. ## Top-down 재귀 구현 가장 설명하기 쉬운 구현은 재귀로 구간을 내려가는 top-down 방식입니다. `tree[node]`가 `[start, end]` 구간의 값을 저장한다고 합시다. `node * 2`는 왼쪽 자식, `node * 2 + 1`은 오른쪽 자식입니다. 구현을 단순하게 하기 위해 `tree` 배열 크기는 보통 `4 * n`으로 잡습니다. ## 구간 질의 구간 `[left, right]`의 합을 구할 때는 현재 노드의 구간 `[start, end]`와의 관계를 봅니다. | 관계 | 처리 | | -------- | ---------------- | | 겹치지 않는다 | 0을 반환 | | 완전히 포함된다 | `tree[node]`를 반환 | | 일부만 겹친다 | 두 자식으로 내려가서 합친다 | 한 질의에서 내려가는 노드는 트리 높이마다 많아야 몇 개씩입니다. 그래서 시간 복잡도는 `O(log n)`입니다. ## 포함되는 구간만 답에 더하기 ![배열 1,2,3,4에서 닫힌 구간 1부터 3까지 질의하면 왼쪽 자식은 일부만 겹쳐 1번 원소까지 내려가고, 오른쪽 자식 2부터 3은 전체 합 7을 그대로 사용합니다. 답은 2 더하기 7인 9입니다.](https://www.readiz.com/assets/lessons/range-structures/segment-query.svg) [그림 크게 보기](https://www.readiz.com/assets/lessons/range-structures/segment-query.svg) · [점 대입과 구간 갱신 실험](https://www.readiz.com/learn/explore/?demo=segment) `[1,2,3,4]`에서 `query(1,3)`의 답은 9입니다. `[0,1]` 노드는 일부만 겹치므로 원소 1까지 내려가고, `[2,3]` 노드는 완전히 포함되어 저장된 7을 바로 반환합니다. 범위 밖인 `[0,0]`은 합의 항등원 0입니다. 그림과 본문의 배열 인덱스는 0부터이고 구간은 \*\*양 끝 포함 `[l,r]`\*\*입니다. 트리 노드 번호는 루트 1부터 시작합니다. 원소 위치와 노드 번호를 서로 바꾸어 읽지 않습니다. ## 점 업데이트 한 위치 `idx`의 값을 `newValue`로 바꿀 때는 leaf까지 내려간 뒤, 돌아오면서 지나온 노드 값을 다시 계산합니다. 변한 위치를 포함하는 노드만 고치면 되므로 점 업데이트도 `O(log n)`입니다. ## Top-down 전체 구현 아래 구현은 비어 있지 않은 0-indexed 배열에서 구간 합과 점 업데이트를 처리합니다. 질의는 `0 <= l <= r < n`, 갱신 위치는 `0..n-1` 범위입니다. > **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다. ```cpp #include using namespace std; struct SegmentTree { int n; vector tree; SegmentTree(const vector& values) { n = (int)values.size(); tree.assign(4 * n, 0); build(1, 0, n - 1, values); } void build(int node, int start, int end, const vector& values) { if (start == end) { tree[node] = values[start]; return; } int mid = (start + end) / 2; build(node * 2, start, mid, values); build(node * 2 + 1, mid + 1, end, values); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } long long query(int left, int right) { return query(1, 0, n - 1, left, right); } long long query(int node, int start, int end, int left, int right) { if (right < start || end < left) return 0; if (left <= start && end <= right) return tree[node]; int mid = (start + end) / 2; return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right); } void update(int idx, long long newValue) { update(1, 0, n - 1, idx, newValue); } void update(int node, int start, int end, int idx, long long newValue) { if (start == end) { tree[node] = newValue; return; } int mid = (start + end) / 2; if (idx <= mid) { update(node * 2, start, mid, idx, newValue); } else { update(node * 2 + 1, mid + 1, end, idx, newValue); } tree[node] = tree[node * 2] + tree[node * 2 + 1]; } }; ``` 입력 구간이 1-indexed라면 `query(l - 1, r - 1)`처럼 바꿔 호출합니다. ## 합 말고 다른 연산일 때 Segment Tree에서 바뀌는 것은 세 가지입니다. 1. 두 자식 값을 합치는 `merge` 2. 구간 밖을 만났을 때 돌려줄 항등원 3. 업데이트 뒤 노드 값을 다시 계산하는 방법 | 질의 | merge | 항등원 | | ------ | ----------- | ------------- | | 구간 합 | `a + b` | `0` | | 구간 최솟값 | `min(a, b)` | 충분히 큰 `INF` | | 구간 최댓값 | `max(a, b)` | 충분히 작은 `-INF` | | 구간 gcd | `gcd(a, b)` | `0` | 이처럼 결합 법칙이 성립하고 항등원이 있는 연산을 monoid로 볼 수 있습니다. Segment Tree는 사실상 "구간을 나눠 monoid 값을 합치는 자료구조"입니다. ## Lazy Propagation 점 하나가 아니라 구간 전체에 값을 더해야 한다면 어떻게 해야 할까요? ```text 1. 구간 [l, r]의 모든 값에 x를 더한다. 2. 구간 [l, r]의 합을 구한다. ``` 구간에 포함된 원소를 하나씩 업데이트하면 한 번에 `O(k log n)`이 걸립니다. Lazy Propagation은 "이 구간 전체에 더해야 할 값이 있다"는 표시를 노드에 남겨 두고, 자식으로 내려갈 때만 밀어 넣는 방식입니다. 구간 합에서 노드 `[start, end]` 전체에 `value`를 더하면 그 노드의 합은 다음만큼 증가합니다. ```text (end - start + 1) * value ``` 아래 구현에서 `lazy[node]`는 현재 노드의 합에도 아직 반영하지 않은 증가량입니다. `push`가 합을 갱신한 뒤 그 증가량을 자식 lazy로 넘깁니다. ## 미뤄 둔 값이 어디에 있는지 확인하기 ![배열 1,2,3,4 전체에 3을 더하면 루트 합은 22이고 자식 합은 3과 7인 채 lazy 3을 가집니다. 왼쪽을 push하면 합 9가 되고 lazy 3이 두 잎으로 전달됩니다.](https://www.readiz.com/assets/lessons/range-structures/segment-lazy.svg) [그림 크게 보기](https://www.readiz.com/assets/lessons/range-structures/segment-lazy.svg) 초기 배열 `[1,2,3,4]`에 `rangeAdd(0,3,3)`을 하면 실제 배열은 `[4,5,6,7]`, 전체 합은 22입니다. 루트의 합은 갱신했지만 두 자식의 합은 아직 3과 7입니다. 각 자식의 `lazy = 3`이 ‘내 담당 원소마다 3을 더해야 한다’는 작업을 보관합니다. 이 상태에서 `query(0,1)`을 하면 왼쪽 자식에 `2 × 3`을 반영해 9를 얻습니다. 이 구현은 겹침 검사 **전에** `push`하므로, 질의에서 제외되는 오른쪽 자식도 방문 시 합이 13으로 갱신됩니다. 답에 더하는 것과 밀린 작업을 처리하는 것은 다른 동작입니다. 실험에서 숫자가 늦게 바뀌는 자식이 있어도 바로 오류는 아닙니다. `tree`와 `lazy`를 함께 해석해야 합니다. 중간 갱신 단계가 끝나기 전에는 다른 질의를 끼워 넣지 않습니다. ## lazy 내려보내기 [원문 lazy 단계 그림 크게 보기](https://www.readiz.com/assets/lessons/range-structures/segment-tree-concept-trace.svg) 재귀로 노드를 방문할 때 먼저 `push`를 호출해 현재 노드에 밀려 있는 값을 처리합니다. 이 함수는 세 가지 일을 합니다. 1. 현재 노드의 합에 밀린 증가량을 반영합니다. 2. leaf가 아니면 자식 lazy에 증가량을 넘깁니다. 3. 현재 노드의 lazy 값을 비웁니다. ## lazy 구간 업데이트 업데이트 구간이 현재 노드를 완전히 덮으면, 그 노드의 lazy만 기록하고 바로 처리합니다. 일부만 겹치면 자식으로 내려갑니다. 완전히 포함되는 노드는 자식까지 내려가지 않습니다. 그래서 구간 업데이트도 `O(log n)`에 가까운 비용으로 처리됩니다. ## lazy 구간 질의 질의도 마찬가지로 방문한 노드에서 `push`를 먼저 호출합니다. `push`를 빼먹으면 부모에는 업데이트가 반영되어 있는데 자식 값은 오래된 상태로 남을 수 있습니다. ## Lazy 전체 구현 아래 구현은 0-indexed 배열에서 구간 덧셈과 구간 합 질의를 처리합니다. 합에는 `구간 길이 × 증가량`이 누적되므로 노드 값과 lazy는 `long long`으로 저장합니다. ```cpp #include using namespace std; struct LazySegmentTree { int n; vector tree; vector lazy; LazySegmentTree(const vector& values) { n = (int)values.size(); tree.assign(4 * n, 0); lazy.assign(4 * n, 0); build(1, 0, n - 1, values); } void build(int node, int start, int end, const vector& values) { if (start == end) { tree[node] = values[start]; return; } int mid = (start + end) / 2; build(node * 2, start, mid, values); build(node * 2 + 1, mid + 1, end, values); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } void push(int node, int start, int end) { if (lazy[node] == 0) return; tree[node] += (end - start + 1) * lazy[node]; if (start != end) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[node] = 0; } void rangeAdd(int left, int right, long long value) { rangeAdd(1, 0, n - 1, left, right, value); } void rangeAdd(int node, int start, int end, int left, int right, long long value) { push(node, start, end); if (right < start || end < left) return; if (left <= start && end <= right) { lazy[node] += value; push(node, start, end); return; } int mid = (start + end) / 2; rangeAdd(node * 2, start, mid, left, right, value); rangeAdd(node * 2 + 1, mid + 1, end, left, right, value); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } long long query(int left, int right) { return query(1, 0, n - 1, left, right); } long long query(int node, int start, int end, int left, int right) { push(node, start, end); if (right < start || end < left) return 0; if (left <= start && end <= right) return tree[node]; int mid = (start + end) / 2; return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right); } }; ``` ## 업데이트 순서가 달라지면 lazy propagation에서는 lazy 값끼리 어떻게 합쳐지는지도 따로 정해야 합니다. | 업데이트 | 노드 값 변화 | lazy 합성 | | -------------- | ------------------------ | -------------------- | | 구간 덧셈 + 구간 합 | `tree += value * length` | 기존 lazy에 더함 | | 구간 덧셈 + 구간 최솟값 | `tree += value` | 기존 lazy에 더함 | | 구간 대입 + 구간 합 | `tree = value * length` | 이전 lazy를 새 대입 값으로 덮음 | | 구간 대입 + 구간 최솟값 | `tree = value` | 이전 lazy를 새 대입 값으로 덮음 | 구간 덧셈과 구간 대입이 동시에 있으면 "대입 뒤 덧셈"과 "덧셈 뒤 대입"의 순서가 결과를 바꿉니다. 이 경우 lazy 상태를 단일 숫자로 두기보다 `hasAssign`, `assignValue`, `addValue`처럼 의미를 분리해 합성 규칙을 명시하는 편이 안전합니다. 빌드는 `O(n)`, 구간 덧셈과 합 질의는 `O(log n)`, 메모리는 `O(n)`입니다. 위 구현은 생성자에 전달한 비어 있지 않은 배열에서 시작합니다. ## 구간 갱신 실습 [창고 구역 장부](https://h.readiz.com/practice/SHELFLOG)에 구간 덧셈·구간 합 구현을 적용할 수 있습니다. 전체 구간을 갱신한 직후 일부 구간을 조회하면 lazy 전달이 맞는지 확인하기 좋습니다. ## 완성 파일로 실행하고 확인하기 [C++17 전체 예제 내려받기](https://www.readiz.com/assets/lessons/range-structures/segment-tree.cpp) ```sh c++ -std=c++17 -O2 segment-tree.cpp -o lesson ./lesson < input.txt ``` 기본 모드는 **구간 덧셈과 구간 합**입니다. `N Q`, N개 초기 값, Q개 연산을 받습니다. `A l r delta`는 `[l,r]`의 모든 값에 delta를 더하고, `Q l r`은 합을 한 줄에 출력합니다. ```text 4 4 1 2 3 4 A 0 3 3 Q 0 1 A 1 2 -2 Q 0 3 ``` 출력은 9와 18입니다. 실험의 기본 예제도 같은 입력입니다. 처음 전체 갱신 뒤 배열은 `[4,5,6,7]`, 두 번째 갱신 뒤에는 `[4,3,4,7]`입니다. 점 대입은 별도 모드로 실행합니다. ```sh ./lesson --point < point.txt ``` 이 모드에서는 `U index newValue`로 한 원소를 새 값으로 바꾸고 `Q l r`로 합을 구합니다. `U 1 -5`는 1번 값에 -5를 **더하는 것이 아니라 -5로 바꾸는 것**입니다. 초기 배열 `[1,2,3,4]`에서 이 갱신 뒤 `Q 1 3`의 답은 2입니다. 두 모드 모두 `1 ≤ N ≤ 200000`, `0 ≤ Q ≤ 200000`, 초기 값·대입 값·delta의 절댓값은 `10^6` 이하입니다. 인덱스는 `0..N-1`, 질의·갱신은 `0 ≤ l ≤ r < N`인 닫힌 구간입니다. 누적 합의 절댓값은 최대 `N × (Q+1) × 10^6 ≤ 4.00002 × 10^16`이어서 `long long` 범위 안입니다. 원소 하나가 작은 값이어도 여러 번 갱신한 **전체 합**을 기준으로 자료형을 정합니다. 파일에는 본문의 기본·lazy 구조체와 `main`이 모두 들어 있습니다. 입력 처리는 빈 배열, 뒤집힌 구간, 범위 밖 인덱스를 거부합니다. 작은 배열을 직접 바꾸고 합산하는 풀이와 비교하고, 전체 갱신 직후 부분 질의, 서로 겹치는 음수 갱신, 한 원소 구간을 확인하세요. [기존 Segment Tree 노트](https://www.readiz.com/notes/data-structure/tree/segmenttree/)는 bottom-up과 XOR 갱신을 다루는 코드 참고입니다. 이 강의의 덧셈 lazy와 XOR lazy는 합성 규칙이 다르므로 그대로 섞지 않습니다. ## 관련 문서 - [Segment Tree](https://www.readiz.com/notes/data-structure/tree/segmenttree/index.md)