세그먼트 트리 Segment Tree

세그먼트 트리란?

여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터 합을 빠르고 간단하게 구할 수 있는 자료구조 

 

세그먼트 트리에서 노드들의 의미

• 리프 노드 : 배열의 구 수 자체
• 리프 노드를 제외한 다른 노드 : 왼쪽 자식과 오른쪽 자식의 최솟값 또는 합을 저장

 

n = 10인 경우 세그먼트 트리는 다음과 같다

 

 

트리 만들기

• 세그먼트 트리는 포화 이진 트리에 가깝기 때문에 배열에 모든 값이 대부분 가득 차게 됨
• 따라서 배열로 트리를 만들어 사용
  • 이 경우 임의의 노드의 인덱스가 i일 때
  • 왼쪽 자식의 인덱스는 2*i
  • 오른쪽 자식의 인덱스는 2*i + 1

 

세그먼트 트리의 구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


// arr : intial array
// tree : segement tree
// node : number of segment tree

long long init(vector<long long> &arr, vector<long long> &tree, int node, int start, int end){
    if (start == end) // current node is leaf node
        return tree[node] = arr[start];
    int mid = (start) + end / 2;
    
    // calculate summation of the range
    return tree[node] = init(arr, tree, node*2, start,mid) + init(arr, tree, node*2+1, mid, end);
    
    // if you want to calculate minimum summation of the range,
    // refer the below code
    // return tree[node] = min(init(arr, tree, node*2, start,mid), init(arr, tree, node*2+1, mid+1, end));
}

long long sum(vector<long long> &tree, int node, int start, int end, int left, int right){
    // case1: [left, right] ∩ [start, end] = ø
    // terminate searching
    if (left > end || right < start)
        return INT_MAX;
    
    // case2: [start, end] ⊂ [left, right]
    if (left <= start && right >= end)
        return tree[node];
    
    // case3: [left, right] ⊂ [start, end]
    // case4: [left, right] ∩ [start, end] != ø
    int mid = (start + end) / 2;
    return sum(tree, node*2, start, mid, left, right) + sum(tree, node*2+1, start, mid+1, left, right);
}

void update(vector<long long> &tree, int node, int start, int end, int index, long long diff){
	// case2: index !⊂ [start, end] 
    if (index < start || index > end)
    	return;
    // case1: index ⊂ [start, end] 
    // update 
    tree[node] = tree[node] + diff;
    
    //if current node isn't leaf, need to change child node
    //so, checking leaf or not, if not, update child node
    if (start != end){
    	int mid = (start + end) / 2;
        update(tree, node*2, start, mid, index, diff);
        update(tree, node*2+1, mid, end, index, diff);
    }
}
    

int main(void){
    
    int N; // size of the array
    vector<long long> arr, tree;
    
    // initialize array to segement tree
    init(arr, tree, 1, 0, N - 1);
    
    // update node
    update(tree, 1, 0, N-1, index, diff);
}