세그먼트 트리

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

시간 복잡도

만약 1~N 까지의 수의 합을 구하려면 선형적으로 계산을 하여야 하기에, 시간 복잡도가 O(N) 이 나온다. 하지만, 트리구조의 특성상, 세그먼트 트리는 O(logN) 이 나온다.

#include <iostream>
using namespace std;
#define NUMBER 12
int tree[4 * NUMBER];
int a[NUMBER] = {1, 9, 3, 8, 4, 5, 5, 9, 10, 3, 4, 5};
int init(int start, int end, int node)
{
    if (start == end)
        return tree[node] = a[start];
    int mid = (start + end) / 2;
    return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}
int sum(int start, int end, int node, int left, int right)
{
    // 범위 밖
    if (end < left || right < start)
        return 0;
    // 범위 안
    if (left <= start && end <= right)
        return tree[node];
    int mid = (start + end) / 2;
    return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}
void update(int start, int end, int node, int index, int dif)
{
    if (index < start || index > end)
        return;
    tree[node] += dif;
    if (start == end)
        return;
    int mid = (start + end) / 2;
    update(start, mid, node * 2, index, dif);
    update(mid + 1, end, node * 2 + 1, index, dif);
}
int main(void)
{
    init(0, NUMBER - 1, 1);
    cout << sum(0, NUMBER - 1, 1, 0, 12) << '\n';
    update(0, NUMBER - 1, 1, 5, -5);
    cout << sum(0, NUMBER - 1, 1, 0, 12) << '\n';
    return (0);
}

[출처] https://m.blog.naver.com/ndb796/221282210534