题解 | #【模板】线段树1#

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
//线段树
struct D {
    int l;
    int r;
    ll sum;
};
int main() {
    int n, q;
    cin >> n >> q;
    vector<int>arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    vector<D>tree(5*n+1);
    function<void(int, int, int)> buildTree = [&](int i, int l, int r) {
        tree[i].l=l,tree[i].r=r;
        if (l == r) {
            tree[i].sum = arr[l];
            return;
        }
        int mid=l+(r-l)/2;
        buildTree(2*i,l,mid);
        buildTree(2*i+1,mid+1,r);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    };
    function<void(int ,int,int)> change=[&](int i,int idx,int num){
        if(tree[i].l==tree[i].r){
            tree[i].sum+=num;
            return ;
        }
        if(tree[i*2].r>=idx){
            change(i*2,idx,num);
        }else{
            change(i*2+1,idx,num);
        }
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    };
    function<ll(int ,int,int)> search=[&](int i,int l,int r){
        if(tree[i].l>=l&&tree[i].r<=r){
            return tree[i].sum;
        }
        ll s=0;
        if(tree[2*i].r>=l){
            s+=search(2*i,l,r);
        }
        if(tree[2*i+1].l<=r){
            s+=search(2*i+1,l,r);
        }
        return s;
    };
    buildTree(1,1,n);
    int flag,a,b;
    while(q--){
        cin>>flag>>a>>b;
        if(flag==1){
            change(1,a,b);
        }
        else{
            cout<<search(1,a,b)<<endl;
        }
    }
}