【单点修改+区间查询】树状数组

树状数组和线段树的区别就是，树状数组好写，没啦 同样的树状数组能实现区间的快速操作，但是根据题目的要求不同树状数组还真不同。

lowbit(int x)

在树状数组中最深奥的一个用法，他能获取二进制x的最后一位

lowbit(x)= x & (-x)

懒得证明，但是肯定是正确的

add(int x,int v)

这段代码的意思是将x位置上的值+v

利用二进制的关系，我们因为需要获取区间的内容，所以我们将x到n的二进制倍数都加上v。

很抽象，但能用就行

void add(int x,int v)
{
  while(x<=n)
  {
    a[x]+=v;
    x+=lowbit(x);
  }
}

getsum(int x)

获取前x的和，利用二进制关系，反着向前将值加上，就是得到的结果

int getsum(int x)
{
  int ans=0;
  while(x)
  {
    ans+=a[x];
    x-=lowbit(x);
  }
  return ans;
}

Code

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x
const int N=5e5+12;
int a[N],n,m;
void add(int x,int v)
{
  while(x<=n)
  {
    a[x]+=v;
    x+=lowbit(x);
  }
}
int getsum(int x)
{
  int ans=0;
  while(x)
  {
    ans+=a[x];
    x-=lowbit(x);
  }
  return ans;
}
int main(){
  cin>>n>>m;
  int p,x,y;
  for(int i=1;i<=n;i++)
  {
    cin>>x;
    add(i,x);
  }
  while(m--)
  {
    cin>>p>>x>>y;
    if( p==1 )
    {
      add(x,y);
    }
    else{
      cout<<getsum(y)-getsum(x-1)<<endl;
    }
  }


}