Segment_tree_template.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = (int)2e5 + 10;
int a[N], t[4 * N];

void pull(int node){
    t[node] = t[2 * node] + t[2 * node + 1];
}

void build(int node, int l, int r){
    if(l == r){
        t[node] = a[l]; return;
    }
    int mid = (l + r) >> 1;
    build(2 * node, l, mid); build(2 * node + 1, mid + 1, r);
    pull(node);
}

int combine(int a, int b){
    return a + b;
}

void update(int node, int l, int r, int val, int i){
    if(l > i || r < i)  return;
    if(l == r){
        t[node] = val;
        a[l] = val; return;
    }
    int mid = (l + r) >> 1;
    update(2 * node, l, mid, val, i); update(2 * node + 1, mid + 1, r, val, i);
    pull(node);
}

int query(int node, int l, int r, int l1, int r1){
    if(l > r1 || r < l1)    return 0; // Change accordingly;
    if(l >= l1 && r <= r1){
        return t[node];
    }
    int mid = (l + r) >> 1;
    return combine(query(2 * node, l, mid, l1, r1), query(2 * node + 1, mid + 1, r, l1, r1));
}

int32_t main(){
   int n; cin >> n;
   for(int i = 1; i <= n; i++)  cin >> a[i];
   build(1, 1, n);
   int q; cin >> q;
   while(q--){
    int type; cin >> type;
    if(type == 1){
        int i, val; cin >> i >> val;
        update(1, 1, n, val, i);
    }else{
        int l, r; cin >> l >> r;
        cout << query(1, 1, n, l, r) << '\n';
    }
   }
   return 0;
}