树状数组的板子

该数据结构可以维护序列的前缀和

1. 单点修改，求区间和

#include <iostream>
using namespace std;
 const int N=5e5+2;
 int n,tr[N];
 int lowbit(int x){
     return x&-x;
 }
 void add(int x,int v){
     for(;x<=n;x+=lowbit(x)) tr[x]+=v;
 }
 int q(int x){
     int t=0;
     for(;x;x-=lowbit(x)) t+=tr[x];
     return t;
 }
 signed main(){
     int i,op,x,y,m;
     scanf("%d%d",&n,&m);
     for(i=1;i<=n;i++) scanf("%d",&x),add(i,x);
     
     while(m--){
         scanf("%d%d%d",&op,&x,&y);
        if(op==1) add(x,y); else printf("%d\n",q(y)-q(x-1));
     }
 }