树状数组

树状数组
本质：快速进行区间单点修改和区间求和的数据结构
复杂度：单次操作复杂度为(logn)
流程：
1.设置lowbit函数
2.单点修改，用while循环修改从这个点起后面一切会影响到的结点，每次加上lowbit自身，跳到下一个2的次方点修改
3.区间和询问，用while循环依次累加对这个点前缀和有影响的节点，每次减去owbit自身，跳到前一个2的次方点累加，再将两前缀和相减得到区间和
原理：
如下图

实现：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tree[500333];
int nn,xx,yy;
int lowbit(int x)
{
 return x & -x;
}
void update(int x,int y)
{
 while(x<=n)
 {
  tree[x]+=y;
  x+=lowbit(x);
 }
}
int query(int x,int y)
{
 int sumx=0,sumy=0;
 x--;
 while(x>0)
 {
  sumx+=tree[x];
  x-=lowbit(x);
 }
 while(y>0)
 {
  sumy+=tree[y];
  y-=lowbit(y);
 }
 return sumy-sumx;
}
int main()
{
 scanf("%d %d",&n,&m);
 for(int i=1;i<=n;i++)
 {
  int k;
  scanf("%d",&k);
  update(i,k);
 }
 while(m--)
 {
  scanf("%d %d %d",&nn,&xx,&yy);
  if(nn==1)
  {
   update(xx,yy);
  }
  if(nn==2)
  {
   cout<<query(xx,yy)<<endl;
  }
 }
 return 0;
}