[알고리즘 공부] 세그먼트 트리

0. 개요

백준에서 여러 알고리즘을 풀다가 빡치면 하단의 알고리즘 분류을 보는 편이다.

그리고 그중에서 가장 많이 본 알고리즘은 바로 세그먼트 트리...였다...

따라서 이번에는 세그먼트 트리의 개념과 구현 예시를 정리할 예정이다.

 

1. 알고리즘 개념

세그먼트 트리는 특정 범위에 대한 질의(구간 합, 최소값, 회대값 등)와 데이터 업데이트를 빠르게 처리하기 위한 이진 트리 기반의 자료구조이다.

가장 대표적인 문제는 백준의 구간합 구하기 문제일 것이다.

 

2. 알고리즘 구조

세그먼트 트리는 완전 이진 트리 형태로 구현되고, 리프 노드는 배열의 원소를 나타낸다.

그리고 모든 내부 노드들은 자식 노드의 구간의 정보를 합친 값을 저장한다.

예를 들어 구간 합을 구할 경우에 부모 노드의 값은 자식 노드들의 합이 저장될 것이고,

최소 값을 구할 경우에는 자식 노드들 중 더 작은 값이 저장될 것이다.

 

3. 알고리즘 핵심 연산

1) 트리 구축하기

배열의 크기 N에 대해 트리를 구성한다.

class SegTree {
	int n;
    vector<int> tree;
    
    SegTree(int n) { init(n); }
    
    SegTree(const vector<int>& a){
    	build(a);
    }
    
    void init(int n)
    {
    	this.n = n;
        tree.assign(4*n, 0);
    }
    
    void build(int node, int l, int r, const vector(int)& a)
    {
    	if(l == r) { tree[node] = a[l]; return; }
        
        int mid = (l + r) / 2;
        build(node * 2, l, mid, a);
        build(node * 2 + 1, mid + 1, r, a);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    
    void build(const vector<int>* a)
    {
    	init((int)a.size());
        if(n > 0) build(1, 0, n-1, a);
    }
}

2) 구간 값 구하기

특정 구간에서의 쿼리를 처리한 값을 구한다.

class SegTree{
	int n;
    vector<int> tree;
    
    ...
    
    // 구간합, [ql, qr] 구간의 합
    int range_sum(int node, int l, int r, ql, qr)
    {
    	if(qr < l || r < ql) return 0; // 안 겹침
        if(ql <= l && r <= qr) return tree[node]; // 완전히 포함됨
        
        int mid = (l + r) / 2;
        return range_sum(node * 2, l, mid, ql,qr) +
        	range_sum(node * 2 + 1, mid + 1, r, ql, qr);
    }
    
    int range_sum(int ql, int qr) {
    	return range_sum(1, 0, n-1, ql, qr);
    }
}

3) 값 갱신하기

배열의 특정 원소 값을 변경한다.

이 경우 해당 노드부터 그 부모 노드까지 모두 값을 갱신한다.

class SegTree {
	int n;
    vector<int> tree;
    
    ...
    
    void update_value(int node, int l, int r, int pos, int value)
    {
    	if(l == r) { tree[node] = value; return; }
        
        int mid = (l + r) / 2;
        if(pos <= mid) update_value(node * 2, l, mid, pos, value);
        else update_value(node * 2 + 1, mid + 1, r, pos, value);
        
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

4. 후기

항상 알고리즘 목록에 세그먼트 트리가 있을 때 간단하게 검색만 하고 넘어가서 정확한 의미를 파악할 수 없었지만,

이번 기회에 확실하게 정리할 수 있어서 좋았다.

구간 값을 구하는 부분에서 살짝 이해가 안됐지만, 실제 시뮬레이션을 돌려보고 의외로 간단한 로직이라는 걸 이해할 수 있었다.