Segment Tree

#include<bits/stdc++.h>
#define endl '\n'
#define INF 999999999

typedef long long int ll;

using namespace std;

//for Dynamic RSQ
class SegmentTree{
    vector <ll> st, A;
    ll n;
    ll left(ll i){return i<<1;}
    ll right(ll i){return (i<<1)+1;}

    void build(ll node, ll start, ll end1){
        if(start==end1){
            st[node]=A[start];
        }else{
            build(left(node), start, (start+end1)/2);
            build(right(node), (start+end1)/2+1, end1);
        }
        st[node]=st[left(node)]+st[right(node)];
    }
    ll rsq(ll node, ll l, ll r, ll i, ll j){
        if(l>j || r<i)return 0;
        if(l>=i && r<=j)return st[node];

        ll p1=rsq(left(node), l, (l+r)/2, i, j);
        ll p2=rsq(right(node), (l+r)/2+1, r, i, j);
        return p1+p2;
    }
    void update(ll node, ll l, ll r, ll idx, ll val){
        if(l==r){
            st[node]+=val;
            A[idx]+=val;
        }else{
            if(l<=idx && idx<=(l+r)/2){
                update(left(node), l, (l+r)/2, idx, val);
            }else{
                update(right(node), (l+r)/2+1, r, idx, val);
            }
            st[node]=st[left(node)]+st[right(node)];
        }
    }

    public:

    SegmentTree(const vector <ll> &_A){
        A=_A;
        n=A.size();
        st.assign(6*n,0);//6*n instead of 4*n
        build(1, 0, n-1);
    }
    ll rsq(ll i,ll j){return rsq(1,0, n-1, i, j);}
    void update(ll idx, ll val){update(1, 0, n-1, idx, val);}
};

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll n,q;
    cin >> n >> q;
    vector <ll> A;
    for(int i=0; i<n; i++)A.push_back(0);
    SegmentTree fan(A);
    int a,b;
    string k;
    while(q--){
        cin >> k >> a >> b;
        if(k=="add"){
            fan.update(a,b);
        }else{
            cout << fan.rsq(a,b) << endl;
        }
    }

}