Segment tree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a;
vector<ll> t;

void build(int v, ll l, ll r) {
    if(r-l==1) {
        t[v] = a[l];
        return;
    }
    ll mid = l + (r-l)/2;
    build(2*v, l, mid);
    build(2*v+1, mid, r);
    t[v] = t[2*v] + t[2*v+1];
    //cerr << v << " " << l << " " << r << endl;
    //printf("t[%d] = %d\n", v, t[v]);
}

ll get(int v, int l,int r,int ql,int qr) {
    if(ql <= l && r <= qr) {
        return t[v];
    }
    if(r <= ql || qr <= l) {
        return 0;
    }
    ll mid = l + (r-l)/2;
    ll ansl = get(2*v, l, mid, ql,qr);
    ll ansr = get(2*v+1, mid, r, ql, qr);
    return ansr+ansl;
}

void update(int v, int l, int r, int k, ll x) {
    //cout << "V: " << v << " k == " << k << " x == " << x << "l == " << l << " r == " << r << "\n";
    if(r-l==1) {
        t[v]+=x;
        return;
    }
    ll mid = l+(r-l)/2;
    if(k < mid) {
        update(2*v, l, mid, k, x);
    }
    else {
        update(2*v+1, mid, r, k, x);
    }
    t[v] = t[2*v] + t[2*v+1];
//
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("rsq2.in", "r", stdin);
    freopen("rsq2.out", "w", stdout);
    ll n, m, p1, p2, type;
    cin >> n >> m;
    a.resize(n+1);
    t.resize(4*n);
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    }
    build(1, 1, n+1);
    for(int i = 0; i < m; i++) {
        cin >> type >> p1 >> p2;
        if(type == 2) {
            //cout << "";
            cout << get(1, 1, n+1, p1, p2+1) << '\n';
        }
        else {
            //cout << p1+a.size()+1 << "\n\n" <<  << "\n\n\n";

            update(1, 1, n+1, p1, p2);
            //for(int j = 1; j <= n*2; j++) {
            //  cout << t[j] << " ";
            //}
            //cout << endl << endl;
        }
    }

    return 0;
}