算法1
二维树状数组+前缀和
选择二维树状数组的原因是:存在单点修改操作+统计
时间复杂度
nmlognlogn
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N=310,M=102;
int tr[N][N][M];
int n,m,q;
int sum[N][N];
void insert(int x, int y, int k,int v)
{
for(int i=x; i<=N; i+=-i&i)
for(int j=y; j<=N; j+=-j&j)
{
tr[i][j][k]+=v;
}
}
int query(int x, int y, int v)
{
int res=0;
for(int i=x; i>0; i-=-i&i)
for(int j=y; j>0; j-=-j&j)
{
res+=tr[i][j][v];
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
int v;
scanf("%d",&v);
sum[i][j]=v;
insert(i,j,v,1);
}
}
scanf("%d",&q);
while(q--)
{
int op,x1,x2,y1,y2,c;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&x1,&y1,&c);
insert(x1,y1,sum[x1][y1],-1);
insert(x1,y1,c,1);
sum[x1][y1]=c;
}
else
{
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
int ans=query(x2,y2,c)+query(x1-1,y1-1,c)-query(x2,y1-1,c)-query(x1-1,y2,c);
printf("%d\n",ans);
}
}
}