本文为树状数组模板。其中，lowbit() 在状压 dp 一文有所介绍。

单点修改，区间查询

树状数组保存的是前缀和。

Update：修改 $x$ 的值（加上 data）。
Query：
- 查询 $[1,x]$ 区间：query(x) 。
- 查询 $[l,r]$ 区间：query(r)-query(l-1) 。

点击查看代码

long long lb(long long x){return x&(-x);}
void update(long long x,long long data)
{
    while(x<=n) 
        c[x]+=data,x+=lb(x);
}
long long query(long long x)
{
	long long ans=0;
	while(x>=1) ans+=c[x],x-=lb(x);
	return ans;
}

区间修改，单点查询

模板题。

可见，本代码和上面的代码有一点点区别。因为这里树状数组上的节点保存了一些修改操作，不再是前缀和。

Query：查询 $x$ 的值（加上之前保存的修改操作）。
Update：
- 修改 $[1,x]$ 区间：update(x,data) 。
- 修改 $[l,r]$ 区间：update(r,data);update(l-1,-data) 。

点击查看代码

long long lb(long long x){return x&(-x);}
void update(long long x,long long data)
{
    while(x>=1) 
        c[x]+=data,x-=lb(x);
}
long long query(long long x)
{
	long long ans=0;
	while(x<=n) ans+=c[x],x+=lb(x);
	return ans;
}

二维树状数组单点修改，矩阵查询

模板题。

树状数组保存的是矩阵前缀和。

Update：修改 $x$ ， $y$ 的值（加上 data）。
Query：
- 查询 $(1,1)-(x,y)$ 矩阵：query(x,y) 。
- 查询 $(x_1,y_1)-(x_2,y_2)$ 矩阵：
  query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1) 。

本题参考代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	int n,m,t[100+10][300+10][300+10],g[300+10][300+10];//t 多一维用来存储种类
	int lb(int x){return x&-x;}
	void update(int x,int y,int type,int data)
	{
		for(int i=x;i<=n;i+=lb(i))
            for(int j=y;j<=m;j+=lb(j))
                t[type][i][j]+=data;
		return;
	}
	int query(int x,int y,int type)
	{
        int ret=0;
		for(int i=x;i;i-=lb(i))
            for(int j=y;j;j-=lb(j))
                ret+=t[type][i][j];
		return ret;
	}
	void yzmain()
	{
		int t1,t2,t3,t4,t5,q;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				scanf("%d",&t1);
				update(i,j,t1,1);
				g[i][j]=t1;
			}
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			scanf("%d",&t1);
			if(t1==1)
			{
				scanf("%d%d%d",&t1,&t2,&t3);
				update(t1,t2,g[t1][t2],-1);
				update(t1,t2,t3,1);
				g[t1][t2]=t3;
			}
			else
			{
				scanf("%d%d%d%d%d",&t1,&t2,&t3,&t4,&t5);
				/*           y      x1  x2  y1  y2  data
				      ---1---2
				     |   |   |
				     1--- ---
				     |   |   |
				   x 2--- ---
				   简单容斥
				*/
				printf("%d\n",query(t2,t4,t5)+query(t1-1,t3-1,t5)-query(t1-1,t4,t5)-query(t2,t3-1,t5));
			}
		}
		return;
	}
}
int main()
{
	_yz::yzmain();
	return 0;
}