백준 2042번 구간 합 구하기

세그먼트 트리를 이용해 구간 합을 구하는 문제였다. 트리의 각 노드에 모든 하위 노드의 합을 저장하여 구간합을 구하는 방식으로 문제를 풀이했다.

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

using namespace std;

typedef long long ll;

ll init(vector<ll> &a, vector<ll> &tree, int start, int end, int node)
{
    if (start == end) return tree[node] = a[start];
    int mid = (start + end) / 2;
   
    return tree[node] = init(a, tree, start, mid, node * 2) + init(a, tree, mid + 1, end, node * 2 + 1);
}


ll sum(vector<ll>& tree, int start, int end, int node, int left, int right)
{
   
    if (left > end || right < start) return 0;
    if (left <= start && right >= end) return tree[node];
    int mid = (start + end) / 2;
    return sum(tree, start, mid, node * 2, left, right) + sum(tree, mid + 1, end, node * 2 + 1, left, right);
}


void update(vector<ll>& tree, int start, int end, int node, int index, ll dif)
{
    // 범위를 벗어난 경우
    if (index < start || index > end) return;
    tree[node] += dif; 
    if (start == end) return; 
    int mid = (start + end) / 2;
    update(tree, start, mid, node * 2, index, dif);
    update(tree, mid + 1, end, node * 2 + 1, index, dif);
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    int h = (int)ceil(log2(n)); 
    int tree_size = (1 << (h + 1)); 
    vector<ll> tree(tree_size);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    init(a, tree, 0, n - 1, 1);
    k += m;
    while (k--)
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        if (t1 == 1)
        {
            t2--; 
            ll dif = (ll)(t3 - a[t2]); 
            a[t2] = t3; 
            update(tree, 0, n - 1, 1, t2, dif);
        }
        else if (t1 == 2)
        {
            cout << sum(tree, 0, n - 1, 1, t2 - 1, t3 - 1) << '\n';
        }
    }
}