题目链接

树状数组

树状数组最基本的就是求区间和。

维护：

• 空间复杂度：O(n)
• 时间复杂度（区间和，单点修改）：

　　　　修改：O(logn)

　　　　查询：O(logn)

用c[i]表示（i-lowbit[i]+1,i）区间的和。

查询时，用到前缀和的思想，(i,j)=c[j]-c[i-1]。

优点

代码简单

缺点

难理解

代码（解析）

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn=500005; 5 int n,m; 6 int c[maxn]; 7 int lowbit(int x){
   //求对应数字的二进制的从后往前的第一个1。  8     return x&(-x);//例如：6(110)->lowbit(6)=2;12(1100)->lowbit(12)=4 9 }10 void update(int x,int v){
   //初始化和更新 11     for(int i=x;i<=n;i+=lowbit(i)){
   //自己手画一下 12         c[i]+=v;13     }14 }15 int query(int x){    //查询：和更新很像，像是互逆的 16     int res=0;17     for(int i=x;i>0;i-=lowbit(i)) res+=c[i];18     return res;19 }20 int main()21 {22     cin>>n>>m;23     for(int i=1;i<=n;i++){24         int v;25         scanf("%d",&v);26         update(i,v);27     }28     for(int i=1;i<=m;i++){29         int k,x,y;30         scanf("%d%d%d",&k,&x,&y);31         if(k==1) update(x,y);32         if(k==2) cout<
       
        <