부분구간의 합

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
ll sum(vector<ll> &tree, int node, int left, int right, int start, int end) {
    /*
    [left,right]와 [start,end]가 겹치지 않는 경우
    [left,right]가 [start,end]를 완전히 포함하는 경우
    [start,end]가 [left,right]를 완전히 포함하는 경우
    [left,right]와 [start,end]가 겹쳐져 있는 경우 (1, 2, 3 제외한 나머지 경우)
    */
    if (left <= start && end <= right) {
        //(1)
        return tree[node];
    }
    else if (start > right || left > end) {
        //[start, end]앞에 있거나, 뒤에 있을 때 
        return 0;
    }
    else {
        return sum(tree, node * 2, left, right, start, (start + end) / 2) + sum(tree, node * 2 + 1, left, right, (start + end) / 2 + 1, end);
    }
}
void update(vector<ll> &tree, int node, int index, int diff, int start, int end) {
    //[start, end]의 범위 안에 있을 때 
    //없을 때
 
    if (start > index || index > end) return; //(2)
    //범위 안에 있을 때는 값을 갱신 
    tree[node] += diff;
 
    if (start != end) {
        update(tree, node * 2, index, diff, start, (start + end) / 2);
        update(tree, node * 2+1, index, diff,(start + end) / 2 + 1, end);
 
    }
}
ll init(vector<ll> &tree, vector<ll> &input, int node, int start, int end) {
    if (start == end) return tree[node] = input[start]; //제자리 찾아감 
    return tree[node] = init(tree, input, node * 2, start, (start + end) / 2) + init(tree, input, node * 2 + 1, (start + end) / 2 + 1, end);
    //왼쪽 자식과 오른쪽 자식을 더한 값을 저장한다.
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m, k;
 
    cin >> n >> m >> k;
 
    //5개짜리의 리프노드-> 포화 이진트리로 만들기 위해서는 2^h+1-1 개의 노드가 필요하다. 
    //h는 이진트리의 높이 (log2)
 
    
 
    int h = (int)ceil(log2(n));
    int tree_size = 1 << (h + 1);
 
    vector<ll> inputs, tree(tree_size);
 
 
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        inputs.push_back(a);
    }
 
    init(tree, inputs, 1, 0, n - 1); //인덱스 트리 만들기 
 
    /*cout << "debug ";
    for (int j = 0; j < tree_size; j++) cout << tree[j] << ' ';
    cout << '\n';*/
 
    for (int i = 0; i < m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c;
 
        if (a == 1) {
            // 값을 변경 
            // 인덱스트리에 변경되는 값은 현재 값에서 바꾸는 값으로 변경되는 만큼의 숫자이다. 
            b--;
            int diff = c - inputs[b];
            inputs[b] = c; //변경될 값을 저장 
 
            //인덱스 트리는 부모노드가 자식노드의 합을 저장하고 있기 때문에 반영해줘야 한다. 
            update(tree, 1, b, diff, 0, n - 1);
            
        }
        else if (a == 2) {
            //구간 합 구하기 
            b--;
            c--;
            cout << sum(tree, 1, b, c, 0, n-1) << '\n';
        }
    }
    return 0;
}