Algorithm in A..Z - Segment Tree

개념

각 노드에 구간의 정보를 저장하여 Query, Update를 빠르게 처리할 수 트리다.

---

작동원리

트리로 구간의 정보를 저장하여 최악의 경우 트리의 높이만큼 트리를 탐색하여 Query와 Update를 수행할 수 있다.

 

트리의 성질

왼쪽 자식노드 : index * 2

오른쪽 자식노드 : index * 2 + 1

 

Query

1. 참조하는 범위가 구간을 완전히 벗어나면 0을 Return한다.
2. 참조하는 범위가 구간에 완전히 겹치면 Tree에 저장된 값을 Return한다.
3. 참조하는 범위가 구간에 걸치면 Tree에 더 깊은 Level을 참조한다.

3-6 구간의 정보를 얻으려면 5, 6을 참조한다.

1-7 구간의 정보를 얻으려면 2, 6, 14를 참조한다.

1-8 구간의 정보를 얻으려면 1을 참조한다.

 

Update

1. 참조하는 범위가 인덱스를 벗어나면 종료한다.
2. 값을 업데이트한다.
3. 참조하는 노드가 단말 노드이면 종료한다.

3의 정보가 바뀌면 1, 2, 5, 10의 값을 Update한다.

5의 정보가 바뀌면 1, 3, 6, 12의 값을 Update한다.

---

시간 복잡도

init : O(NlogN)

query : O(logN)

update : O(logN)

---

문제

www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<long long> ve, tree;

long long init(int index, int left, int right) {
    if (left == right) {
        return tree[index] = ve[left];
    }

    return tree[index] = init(index * 2, left, (left + right) / 2) + init(index * 2 + 1, (left + right) / 2 + 1, right);
}

long long query(int index, int left, int right, int begin, int end) {
    if (right < begin || left > end) {
        return 0L;
    }

    if (begin <= left && right <= end) {
        return tree[index];
    }

    return query(index * 2, left, (left + right) / 2, begin, end) + query(index * 2 + 1, (left + right) / 2 + 1, right, begin, end);
}

void update(int index, int left, int right, int pos, long long diff) {
    if (pos < left || pos > right) {
        return;
    }

    tree[index] += diff;
    if (left != right) {
        update(index * 2, left, (left + right) / 2, pos, diff);
        update(index * 2 + 1, (left + right) / 2 + 1, right, pos, diff);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> k;

    ve.resize(n);
    for (int i = 0;i < n;++i) {
        cin >> ve[i];
    }

    tree.resize(1 << ((int)ceil(log2(n)) + 1));
    init(1, 0, n - 1);

    for (int i = 0;i < m + k;++i) {
        int a;
        cin >> a;

        if (a == 1) {
            int b;
            long long c;
            cin >> b >> c;

            update(1, 0, n - 1, b - 1, c - ve[b - 1]);
            ve[b - 1] = c;
        } else {
            int b, c;
            cin >> b >> c;

            cout << query(1, 0, n - 1, b - 1, c - 1) << "\n";
        }
    }
}