[BOJ] 구간 합 구하기

[BOJ] 구간 합 구하기

Problem URL : 구간 합 구하기

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
long long init(vector<long long>& a, vector<long long>& tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    } else {
        return tree[node] = init(a, tree, node * 2, start, (start + end) / 2) + init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end);
    }
}
void update(vector<long long>& tree, int index, long long diff) {
    tree[index] = tree[index] + diff;
    while (index > 0) {
        index /= 2;
        tree[index] += diff;
    }
}
long long sum(vector<long long>& 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];
    }
    return sum(tree, node * 2, start, (start + end) / 2, left, right) + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
}
int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h + 1));
    int leaf_num = (1 << h);
    vector<long long> a(leaf_num);
    vector<long long> tree(tree_size);
    m += k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    init(a, tree, 1, 0, leaf_num - 1);
    while (m--) {
        int t1, t2, t3;
        cin >> t1;
        if (t1 == 1) {
            int t2;
            long long t3;
            cin >> t2 >> t3;
            long long diff = t3 - a[t2 - 1];
            a[t2 - 1] = t3;
            update(tree, leaf_num + t2 - 1, diff);
        } else if (t1 == 2) {
            int t2, t3;
            cin >> t2 >> t3;
            cout << sum(tree, 1, 0, leaf_num - 1, t2 - 1, t3 - 1) << "\n";
        }
    }
    return 0;
}

Comments

이 블로그 를 참조해서 좀 더 최적화시켰다.