模板题
注意:
1.树状数组下标要从一开始,不然会死循环
2.树状数组修改循环要到S而不是S-1
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
LL c[1050][1050];
int N;
int lowbit(int n){
return n&(-n);
}
void add(int x,int y,int n){
for(int i=x;i<=N;i+=lowbit(i)){
for(int j=y;j<=N;j+=lowbit(j)){
c[i][j]+=n;
}
}
}
LL sum(int x,int y){
if(x<0||y<0) return 0;
LL res=0;
for(int i=x;i;i-=lowbit(i)){
for(int j=y;j;j-=lowbit(j)){
res+=c[i][j];
}
}
return res;
}
LL query(int l,int b,int r,int t){
return sum(r,t)+sum(l-1,b-1)-sum(r,b-1)-sum(l-1,t);
}
int main(){
int ord;
while(~scanf("%d",&ord)){
if(ord==0){
scanf("%d",&N);
memset(c,0,sizeof(c));
}
else if(ord==1){
int x,y,a;
scanf("%d%d%d",&x,&y,&a);
add(x+1,y+1,a);
}
else if(ord==2){
int l,b,r,t;
scanf("%d%d%d%d",&l,&b,&r,&t);
printf("%lld\n",query(l+1,b+1,r+1,t+1));
}
else break;
}
return 0;
}
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。