二维树状数组poj1195

时间:2025-03-16 09:36:37

题目链接:https://vjudge.net/problem/POJ-1195

题意:一开始输入0和一个s,0代表开始,s代表这是一个s*s的图,接下来会输入1或2,1代表进行单点修改,后面会接3个数字x,y,value,表示把坐标(x,y)增加value,如果是2则代表区间查询,后面会跟两个点的坐标x1,y1,x2,y2,查询这两个点中间区间的区间和。我做的第一道二维数组的题目,感觉有点坑。

不知道二维数组,但是知道一维的可以这篇博客:https://blog.****.net/z309241990/article/details/9615259

一维也不清楚的大胸弟可以看这篇:https://blog.****.net/int64ago/article/details/7429868

这里比较坑的就是区间求和,对于两个点(x1,y1)(x2,y2)中间区间的区间和是这样的

sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1);会减去重复部分,所以要加回来,这个画图还是可以理解的,一开始可能反应不过来,为了防止死循环,我把每个点的横纵坐标都加一,比较安全。

代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn (1<<10)+2
LL a[maxn][maxn];
int n,m,k,t;
int op,x1,x2,yy1,y2,value;
int lowbit(int x){
return x&(-x);
}
void add(int x,int y,int value){//二维树状数组单点修改
for(int i=x;i<maxn;i+=lowbit(i)){
for(int j=y;j<maxn;j+=lowbit(j)){
a[i][j]+=value;
}
}
}
LL sum(int x,int y){//二维树状数组区间求和
LL ans=;
for(int i=x;i>;i-=lowbit(i)){
for(int j=y;j>;j-=lowbit(j)){
ans+=a[i][j];
}
}
return ans;
}
int main()
{
while(scanf("%d",&op)!=EOF){
scanf("%d",&n);
memset(a,,sizeof(a));
while(scanf("%d",&op)&&op!=){
if(op==){
scanf("%d%d%d",&x1,&yy1,&value);
x1++;
yy1++;
add(x1,yy1,value);
}else if(op==){
scanf("%d%d%d%d",&x1,&yy1,&x2,&y2);
x1++;
yy1++;
x2++;
y2++;
LL ans=sum(x2,y2)-sum(x1-,y2)-sum(x2,yy1-)+sum(x1-,yy1-);
printf("%lld\n",ans);
}
}
}
return ;
}