本文共 2280 字，大约阅读时间需要 7 分钟。

树状数组是一种支持单点修改和区间查询的数据结构，

结构如下（用二进制表示，方便查看）：

 先定义一个函数lowbit（i）这个函数返回的值就是i的二进制下从右到左的第一个1保留其他全部变为0所对应的数值，举个例子：14的二进制1110，我们把从右到左的第一个1保留，其他全变为0就是0010，值也就是2，我们发现如果i+lowbit（i）得到的数就是它父亲的位置，i-lowbit(i)就可以找到他的儿子的位置，有什么用呢？这样我们就可以从父亲到儿子，也可以从儿子到兄弟。

int lowbit(int i){	return i&(-i);}

 对于操作: x & -x， 其-x 在计算机存储是用x的补码存储即，~x + 1

构树：对于树状数组从二进制角度看，设a为题目给的数列，c是我们的树状数组。对于c中的每一个我们可以看成一个树的节点，而对应二进制的拆分以及a中对应的数（例如c[16(10000)]就可以拆成c[8(1000)]、c[12(1100)]、c[14(1110)]、c[15(1111)]以及a[16(10000)]）拆分是怎么分的？其实很简单对于一个数，从右往左找到第一个1，把这个1变成0，然后这个位置右边的0不断地依次变成1，这样就可以构成树了。（这种理解方法很好，感谢dalao），空间是O(n)；

查询：我们可以发现要查询[1，i]（[i,j]可以看成[1,j]-[1,i-1]）有两种情况，一，i刚好是2的次方倍，直接输出；二不是2的次方倍，那该怎么办呢？我们根据上面的图发现其实就是i以及比i小的兄弟的和，那么我们直接根据lowbit函数找到兄弟。

int query(int i)//查询区间【1，i】的和{	int ans=0;	while(i>0)	{		ans+=c[i];		i-=lowbit(i);	}	return ans;}

修改：我们如果改动一个数的值，根据图我们可以发现影响到的一定只有它的祖先，所以我们只要修改它本身和祖先就好了。

修改和建树是一起的，初始化为0，每次输入当作修改处理就行。

void change(int i,int num)//修改{	while(i<=n)	{		c[i]+=num;		i+=lowbit(i);	}	return ;}

洛谷上的一道板子题：

#include
   
    #include
    
     using namespace std;int c[500100],n;int lowbit(int i){	return i&(-i);}void change(int i,int num)//修改{	while(i<=n)	{		c[i]+=num;		i+=lowbit(i);	}	return ;}int query(int i)//查询{	int ans=0;	while(i>0)	{		ans+=c[i];		i-=lowbit(i);	}	return ans;}int main(){    ios::sync_with_stdio(false);	int m;	cin>>n>>m;	for(int i=1;i<=n;i++)//输入数据	{		int x;		cin>>x;		change(i,x);//直接当成修改处理	}	for(int i=1;i<=m;i++)	{		int b,x,k;		cin>>b>>x>>k;//输入查询或修改		if(b==1)			change(x,k);//修改		else		{			int ans;			ans=query(k)-query(x-1);//查询			cout<
     
      <
     
    
   

那区间修改和单点查询呢？可以用树状数组维护差分，我们新增一个数组a表示修改的差分然后直接在（修改范围是[i,j]）i上加k（k是修改值），j-1上加-k这样就修改好了，查询就是差分的前缀和加上自己本身的值。

#include
   
    #include
    
     using namespace std;int c[500100],n,b[500100];int lowbit(int i){	return i&(-i);}void change(int i,int num)//修改{	while(i<=n)	{		c[i]+=num;		i+=lowbit(i);	}	return ;}int query(int i)//查询{	int ans=0;	while(i>0)	{		ans+=c[i];		i-=lowbit(i);	}	return ans;}int main(){    ios::sync_with_stdio(false);	int m;   cin>>n>>m;   for(int i=1;i<=n;i++)   {   	cin>>b[i];//输入数据   }   for(int i=1;i<=m;i++)   {   	int d,x,y,k;   	cin>>d;   	if(d==1)   	{   		cin>>x>>y>>k;//修改区间   		change(x,k);   		change(y+1,-k);   	}   	else   	{   		cin>>x;   		int ans;   		ans=query(x);//单点查询   		cout<
     
      <