首页 > 代码库 > 二维树状数组
二维树状数组
修改
void change(int i, int j, int delta){
A[i][j] += delta;
for(int x = i; x < A.length; x += lowbit(x))
for(int y = j; y < A[i].length; y += lowbit(y))
C[x][y] += delta;
}
查询
int getsum(int i, int j){
int res = 0;
for(int x = i; x; x -= lowbit(x))
for(int y = j; y; y -= lowbit(y))
res += C[x][y];
return res;
}
子矩阵 (x1, y1) ~ (x2,y2) 的和，我们只需四个矩阵容斥就可以解决：
Ans = sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1)
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
//int A[1005][1005];
int C[1005][1005];
int n,t,x1,y1,x2,y2;
int lowbit(int x)
{
return x&(-x);
}
void change(int x,int y,int delta)
{
//A[i][j]+=delta;
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
C[i][j]+=delta;
}
int getsum(int x,int y)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
res+=C[i][j];
return res;
}
//子矩阵(x1,y1)~(x2,y2)的和，只需要四个矩阵容斥即可
//Ans=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1)
int main()
{
memset(C,0,sizeof(C));
scanf("%d%d",&n,&t);
char op[10];
while(t--)
{
scanf("%s",&op);
if(op[0]==‘C‘)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
change(x1,y1,1);
change(x2+1,y1,1);
change(x1,y2+1,1);
change(x2+1,y2+1,1);
}
else
{
scanf("%d%d",&x1,&y1);
if(getsum(x1,y1)%2==0) printf("0\n");
else printf("1\n");
}
}
return 0;
}
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
//int A[1005][1005];
int C[1005][1005];
int n,t,x1,y1,x2,y2,add;
int lowbit(int x)
{
return x&(-x);
}
void change(int x,int y,int delta)
{
//A[i][j]+=delta;
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
C[i][j]+=delta;
}
int getsum(int x,int y)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
res+=C[i][j];
return res;
}
//子矩阵(x1,y1)~(x2,y2)的和，只需要四个矩阵容斥即可
//Ans=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1)
int main()
{
memset(C,0,sizeof(C));
scanf("%d%d",&n,&t);
char op[10];
while(t--)
{
scanf("%s",&op);
if(op[0]==‘C‘)
{
scanf("%d%d%d",&x1,&y1,&add);
change(x1,y1,add);
}
else
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1));
}
}
return 0;
}
二维树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。