세그먼트 트리

배열을 완전 이진 트리 형태로 표현해, 구간 질의(query)와 단일 인덱스 갱신(update)을 모두 O(log n)에 처리하는 자료구조입니다.

동작 과정

arr = [1, 3, 5, 7, 9, 11]   (index 0~5, n=6)

tree[node]는 node가 담당하는 구간 [start, end]의 합이다.
노드 번호: 루트=1, 왼쪽 자식=node*2, 오른쪽 자식=node*2+1

                    1,[0,5]=36
                   /            \
         2,[0,2]=9                3,[3,5]=27
         /       \                 /       \
  4,[0,1]=4    5,[2,2]=5    6,[3,4]=16   7,[5,5]=11
   /    \                     /    \
8,[0,0]=1 9,[1,1]=3   12,[3,3]=7 13,[4,4]=9

query(left=1, right=4)  — arr[1..4] = 3+5+7+9 = 24

node=1,[0,5]: 질의 구간에 일부만 걸침 → 양쪽 자식 재귀
  node=2,[0,2]: 일부만 걸침(1~2) → 양쪽 자식 재귀
    node=4,[0,1]: 일부만 걸침(1) → 왼쪽(node=8,[0,0])은 범위 밖, 오른쪽(node=9,[1,1])은 완전 포함 → 3
    node=5,[2,2]: 완전 포함 → 5
    반환 = 3 + 5 = 8
  node=3,[3,5]: 일부만 걸침(3~4) → 양쪽 자식 재귀
    node=6,[3,4]: 완전 포함 → 16
    node=7,[5,5]: 완전히 범위 밖 → 0
    반환 = 16 + 0 = 16
  반환 = 8 + 16 = 24  ✔

update(index=2, newValue=10)  — arr[2]: 5 → 10

리프까지 내려가 값을 바꾸고, 올라오면서 거쳐온 조상 노드만 다시 합산한다.

node=1,[0,5] → mid=2, index(2)<=mid → 왼쪽(node=2,[0,2])
node=2,[0,2] → mid=1, index(2)>mid  → 오른쪽(node=5,[2,2])
node=5,[2,2] → leaf: tree[5] = 5 → 10

복귀하며 재계산:
  tree[2] = tree[4] + tree[5] = 4 + 10 = 14
  tree[1] = tree[2] + tree[3] = 14 + 27 = 41

결과: arr = [1,3,10,7,9,11], 전체 합 tree[1]=41 (1+3+10+7+9+11=41 ✔)

구현

class SegmentTree {
    int[] tree;
    int n;

    SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];   // 완전 이진 트리가 아닐 수 있어 넉넉히 4n
        build(arr, 1, 0, n - 1);
    }

    void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        build(arr, node * 2, start, mid);
        build(arr, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    // arr[left..right] 구간 합
    int 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);
    }

    // arr[index] = value로 갱신
    void update(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = value;
            return;
        }
        int mid = (start + end) / 2;
        if (index <= mid) {
            update(node * 2, start, mid, index, value);
        } else {
            update(node * 2 + 1, mid + 1, end, index, value);
        }
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

// 사용: query(1, 0, n - 1, left, right), update(1, 0, n - 1, index, value)

복잡도

연산복잡도근거
buildO(n)전체 노드를 한 번씩만 채운다
queryO(log n)질의 구간과 겹치는 경로만 방문, 트리 높이가 log n
updateO(log n)리프까지 내려가는 경로 + 올라오며 재계산하는 경로 모두 트리 높이만큼
공간O(n)tree 배열 크기 4n

주의사항

핵심 정리

CSLOG에서 보기