前往：我自己搭建的博客
题目
洛谷P3374树状数组 1
题解
能够用树状数组维护的值必须满足区间加（将两个区间合并）和区间减（将一个区间拆开）（例：区间和可以加减，但区间最值只能加不能减）。树状数组的作用是动态维护区间数据和动态查询，基本用途是维护区间和（以下讲解都以区间和为例）。
lowbit运算：lowbit(n)定义为非负整数n在二进制表示下“最低位的1和其后面所有的0”构成的数值。（例子：n=10=(1010),lowbit(n)=2=(10) ）
C++中，在补码表示下,~n=-1-n, lowbit(n)=n&(~n+1)=n&(-n)。
另c[x]表示序列的区间[x-lowbit(x)+1,x]中的所有数的和，于是区间[1,x]就可以分为(log x)段，相当于二进制分解的过程。（例：x=7=(111),[1,7]分成[1,4],[5,6],[7,7]，区间长度分别为4,2,1）
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int n,m;
int sum[maxn];
inline int lowbit(int x) {return x&(-x);}
inline void add(int x,int y) //给第x个位置加y
{
for( ;x<=n;x+=lowbit(x)) sum[x]+=y;
}
inline int ask(int x) //查询区间[1,x]的和
{
int ans=0;
for( ;x;x-=lowbit(x)) ans+=sum[x];
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x; scanf("%d",&x);
add(i,x);
}
for(int i=1;i<=m;i++)
{
int t,x,y; scanf("%d%d%d",&t,&x,&y);
if(t==1) add(x,y);
else {int ans=ask(y)-ask(x-1); printf("%d\n",ans);}
}
return 0;
}
