세그먼트 트리에 대해 간단히 정리합니다.

참고 : cp-algorithms.com

세그먼트 트리

Segment Tree는 배열의 구간 쿼리를 효율적으로 구해줄 수 있는 데이터 구조입니다. 또한 배열의 어떤 값을 바꿔도 효율적으로 업데이트가 가능합니다. 합에 대한 쿼리를 처리하는 세그먼트 트리를 예로 들겠습니다.

construct(build)

• 메모리
  배열의 크기를 n이라 활 때 4*n개의 칸이 필요합니다.
  각 노드는 최대 2개의 자식을 가지고 트리의 높이는 log(n)입니다.
  따라서 1+2+4+⋯+2⌈log2n⌉=2(⌈log2n⌉+1)<4n.

build 알고리즘

• leaf노드 일때
  트리[현재 노드] =배열[현재 노드]

• leaf 노드가 아닐 때

  1. 재귀적으로 왼쪽,오른쪽 자식에 대해 build 호출
  2. 트리[현재 노드] =트리[왼쪽 자식]+트리[오른쪽 자식]

• 소요 시간 : O(n)

Sum queries

구간 합의 계산은 트리를 순회하며 이루어집니다. 루트 노드에서 시작해서 필요한 범위들에 대해 구간합을 구하도록 합니다.

sum query 알고리즘

루트에서 시작해서 원하는 구간의 합을 구하도록 요청합니다.

• (구현 레벨에서 일어날 수 있는) l>r인 경우
  return 0을 해줍니다.
  

• 현재 구간이 원하는 구간과 꼭 일치할 때
  현재 노드에 저장된 이미 계산된 값을 리턴합니다.
  

• 현재 구간이 원하는 구간과 일치하지 않을 때
  두 자식 구간에 합 계산을 요청합니다.

• 소요 시간 : O(log n)
  최대 4log(n)개의 노드를 방문하기 때문에 O(log n)의 시간복잡도입니다.
  

update queries

a[i]는 트리의 한 레벨에서 하나의 세그먼트에만 영향을 줍니다.
트리에서 a[i]값은 최초에 leaf 노드에 있습니다. 자식들은 트리에서 왼쪽 자식이거나 오른쪽 자식 둘 중 하나이기 때문에 하나의 세그먼트에만 영향을 줍니다.

update 알고리즘

루트노드에서 시작해서 변경할 인덱스를 찾아서 재귀적으로 쭉 내려갑니다. 다 내려갔으면 재귀가 풀리면서 반환될 때 관련 구간을 업데이트합니다. 호출된 함수들이 스택에 쭉 푸시된 다음 팝되는 이미지를 상상하시면 이해가 편합니다.

• 소요 시간 : O(log n)

Implementation

실제로 트리 구조를 저장하지 않습니다. 이진 트리이기 때문에 배열로 처리할 수 있습니다. 루트 노드는 1번, i번째 자식의 왼쪽 자식은 2i, 오른쪽 자식은 2i+1로 둘 수 있습니다.

#include <bits/stdc++.h>

#define pii pair<int,int>
#define fs first
#define sc second
#define all(v) v.begin(),v.end()
#define sorta(a) sort(all(a))

using namespace std;
typedef long long ll;

#define debug(a) for(auto x:a) cout<<x<<' '; cout<<'\n';

// given array : a
// segment Tree : t

const int MAX=1e6+100;
ll n,t[MAX*4];

void build(ll a[], int v, int tl, int tr) {
    if(tl==tr){
        t[v]=a[tl];
    }else{
        int tm=(tl+tr)/2;
        build(a,v*2,tl,tm);
        build(a,v*2+1,tm+1,tr);
        t[v]=t[v*2]+t[v*2+1];
    }
}

// v : current vertex
//tl,tr : boundaries of current vertex
//l,r : boundaries of query
ll sum(int v,int tl,int tr,int l,int r){
    if(l>r) return 0;
    if(l==tl && r==tr) return t[v]; //구하는 쿼리와 이 노드가 저장하는 범위가 꼭 일치할 때만 값 리턴
    else{   //아니면 일단 아래 자식들한테 요청
        int tm=(tl+tr)/2;
        //left child + right child
        return sum(v*2,tl,tm,l,min(tm,r)) + sum(v*2+1,tm+1,tr,max(tm+1,l),r);
    }
}

void update(int v,int tl,int tr,int pos,ll val){
    if(tl==tr){
        t[v]=val;
    }else{
        int tm=(tl+tr)/2;
        if(pos<=tm){
            update(2*v,tl,tm,pos,val);
        }else{
            update(2*v+1,tm+1,tr,pos,val);
        }
        t[v]=t[v*2]+t[v*2+1];
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int m,k; 
    cin>>n;
    cin>>m>>k;
    ll* a= new ll[n];
    for(int i=0;i<n;i++) cin>>*(a+i);
    
    build(a,1,0,n-1);

    for(int i=0;i<m+k;i++){
        ll c,l,r; cin>>c>>l>>r;
        
        if(c==1) update(1,0,n-1,l-1,r);
        else {
            l--,r--;
            cout<<sum(1,0,n-1,l,r)<<'\n';
        }
        
    }
}

Advanced versions of Segment Trees

여러 응용이 가능합니다.

• Finding the maximum and the number of times it appears

• Compute the greatest common divisor / least common multiple

• Counting the number of zeros, searching for the k-th zero

• Finding subsegments with the maximal sum

Finding subsegments with the maximal sum

트리의 각 노드에 4가지 정보를 저장합니다.
구간의 합, max prefix sum, max suffix sum, 앞의 세 값들 중 최대값
구하는 값의 경우는 기본 세그먼트 트리의 논리와 동일하게 다음 3가지 경우입니다.
1. 왼쪽 자식에 최대값이 존재
2. 오른쪽 자식에 최대값이 존재
3. 왼쪽,오른쪽 자식이 겹친 구간에 최대값이 존재

따라서 구하는 값은 위 3값 중 최대값입니다.
구조체를 만들고 적절한 wrapper 함수를 만들어서 기본 세그먼트 트리와 비슷하게 구현할 수 있습니다.