Segment Tree: 구간 합과 미룬 갱신

Fenwick Tree에서는 정해진 prefix 구간을 모아 합을 구했습니다. 이번에는 배열을 반씩 나눈 구간에서 답을 합칩니다. 점 하나를 새 값으로 바꾸는 연산과 구간 전체에 값을 더하는 연산을 구분하고, 후자의 작업을 자식에게 미루는 과정을 따라갑니다.

배열 값이 바뀌는 동안 구간 합·최솟값·최댓값을 묻는다면, 구간을 반으로 나눈 트리에 결과를 저장할 수 있습니다. 바뀐 위치를 포함하는 구간만 고쳐 점 갱신과 구간 질의를 O(log n)에 처리합니다.

구간을 반으로 나누는 트리

Segment Tree의 각 노드는 배열의 한 구간을 담당합니다.

[0, 7]
├─ [0, 3]
│  ├─ [0, 1]
│  └─ [2, 3]
└─ [4, 7]
   ├─ [4, 5]
   └─ [6, 7]

루트는 전체 구간을 담당하고, 자식은 구간을 절반씩 나누어 담당합니다. 길이가 1인 구간이 leaf입니다.

구간 합 Segment Tree라면 각 노드는 자신이 담당하는 구간의 합을 저장합니다.

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]에서 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 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

#include <vector>
using namespace std;

struct SegmentTree {
    int n;
    vector<long long> tree;

    SegmentTree(const vector<long long>& 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<long long>& 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

점 하나가 아니라 구간 전체에 값을 더해야 한다면 어떻게 해야 할까요?

1. 구간 [l, r]의 모든 값에 x를 더한다.
2. 구간 [l, r]의 합을 구한다.

구간에 포함된 원소를 하나씩 업데이트하면 한 번에 O(k log n)이 걸립니다. Lazy Propagation은 “이 구간 전체에 더해야 할 값이 있다”는 표시를 노드에 남겨 두고, 자식으로 내려갈 때만 밀어 넣는 방식입니다.

구간 합에서 노드 [start, end] 전체에 value를 더하면 그 노드의 합은 다음만큼 증가합니다.

(end - start + 1) * value

아래 구현에서 lazy[node]는 현재 노드의 합에도 아직 반영하지 않은 증가량입니다. push가 합을 갱신한 뒤 그 증가량을 자식 lazy로 넘깁니다.

미뤄 둔 값이 어디에 있는지 확인하기

그림 크게 보기

초기 배열 [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 단계 그림 크게 보기

재귀로 노드를 방문할 때 먼저 push를 호출해 현재 노드에 밀려 있는 값을 처리합니다.

이 함수는 세 가지 일을 합니다.

1. 현재 노드의 합에 밀린 증가량을 반영합니다.
2. leaf가 아니면 자식 lazy에 증가량을 넘깁니다.
3. 현재 노드의 lazy 값을 비웁니다.

lazy 구간 업데이트

업데이트 구간이 현재 노드를 완전히 덮으면, 그 노드의 lazy만 기록하고 바로 처리합니다. 일부만 겹치면 자식으로 내려갑니다.

완전히 포함되는 노드는 자식까지 내려가지 않습니다. 그래서 구간 업데이트도 O(log n)에 가까운 비용으로 처리됩니다.

lazy 구간 질의

질의도 마찬가지로 방문한 노드에서 push를 먼저 호출합니다.

push를 빼먹으면 부모에는 업데이트가 반영되어 있는데 자식 값은 오래된 상태로 남을 수 있습니다.

Lazy 전체 구현

아래 구현은 0-indexed 배열에서 구간 덧셈과 구간 합 질의를 처리합니다. 합에는 구간 길이 × 증가량이 누적되므로 노드 값과 lazy는 long long으로 저장합니다.

#include <vector>
using namespace std;

struct LazySegmentTree {
    int n;
    vector<long long> tree;
    vector<long long> lazy;

    LazySegmentTree(const vector<long long>& 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<long long>& 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)입니다. 위 구현은 생성자에 전달한 비어 있지 않은 배열에서 시작합니다.

구간 갱신 실습

창고 구역 장부에 구간 덧셈·구간 합 구현을 적용할 수 있습니다. 전체 구간을 갱신한 직후 일부 구간을 조회하면 lazy 전달이 맞는지 확인하기 좋습니다.

완성 파일로 실행하고 확인하기

C++17 전체 예제 내려받기

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은 합을 한 줄에 출력합니다.

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]입니다.

점 대입은 별도 모드로 실행합니다.

./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 노트는 bottom-up과 XOR 갱신을 다루는 코드 참고입니다. 이 강의의 덧셈 lazy와 XOR lazy는 합성 규칙이 다르므로 그대로 섞지 않습니다.

curl -fsSL 'https://www.readiz.com/records/segment-tree/index.md'