세그먼트 트리(Segment-Tree)코드

내가 문제풀때 볼려고 쓴 글입니다.

 

나를 위한 팁

1. 트리는 배열로 구현하는데, PS시 배열의 크기를 맞게 할 필요는 없으므로, 넉넉하게 하자.

2. 세그먼트 트리를 항상 Sum으로 할 필요는 없다. 상황에 잘 맞게 운용할수 있는걸 명심하자.

(초기화 방법)segment tree

int h = (int)ceil(log2(n));
 int tree_size = (1 << (h+1)); 
//  tree_size
// 트리 사이즈를 ps에서는 그냥 넉넉하게 준비하자 위처럼하면 골치아프다

ll init(vector<ll> &arr, vector<ll> &tree, int node, int start, int end)
{//트리는 배열로 표현, arr은 트리가 아닌  단순 선형 배열
    if (start == end)
        return tree[node] = arr[start];

    int mid = (start + end) / 2;

    return tree[node] = init(arr, tree, node * 2, start, mid) + init(arr, tree, node * 2 + 1, mid + 1, end); 
//왼쪽부분 + 오른쪽 부분 
//제귀적으로 계속 밑으로  가서  밑바닥 도달햇을때,  start == end가 됬다면  초기화 하기,
}

Update

(갱신과정)

void update(vector<ll> &tree, int node, int start, int end, int index, ll diff)
{
    if (!(start <= index && index <= end))
        return;

    tree[node] += diff;

    if(start != end)
    {
        int mid = (start + end) / 2;
        update(tree, node * 2, start, mid, index, diff);
        update(tree, node * 2 + 1, mid + 1, end, index, diff);
    }
}

Sum

(합과정)

ll tree_sum(vector<ll> &tree, int node, int start, int end, int left, int right)
{
    if (left > end || right < start)
        return 0;

    if (left <= start && end <= right)
        return tree[node];

    int mid = (start + end) / 2;
    return tree_sum(tree, node * 2, start, mid, left, right) + tree_sum(tree, node*2+1, mid+1, end, left, right);
}
// sum = left~ right's sum