在二维平面内给定n个点:
0 x y v表示给(x,y)的权值减去v
1 x y v表示给(x,y)的权值加上v
然后有m个操作
0 x y v , 1 x y v 意义如上
2 a b c d表示询问左上角为(a,b) , 右下角为(c,d)的矩阵权值和
输入格式:
第一行一个数n
后n行 每行三个数 type x y 意义见上
然后一个数m表示操作数
后m行 第一个数为type
若type=2 则接四个数 a,b,c,d 意义见上
否则接三个数 x,y,v 意义见上
输出格式:
对每一个 2号操作输出一个答案
输入样例#1:
8
0 8 10 1
0 8 6 9
0 10 2 48
0 4 8 21
1 6 6 75
0 4 4 23
1 2 9 12
0 4 10 2
9
2 7 2 10 8
1 4 2 92
2 2 4 6 4
0 6 10 29
0 10 8 42
2 4 4 6 6
2 6 6 10 10
2 1 6 8 8
2 8 1 8 2
输出样例#1:
-57
-23
52
-6
45
0
n,m<=100000 ; x,y<=1000
还是由于出题人不会造数据 保证数据全是随机
二维树状数组,,
比较有意思,
和一维的差不多,
就是多了层循环
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 //#define lowbit(x) (x)&(-x)
6 using namespace std;
7 const int MAXN=1010;
8 inline void read(int &n)
9 {
10 char c='+';bool flag=0;n=0;
11 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
12 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
13 }
14 int tree[MAXN][MAXN];
15 int maxn=1000;
16 inline int lowbit(int x) {return x&(-x);}
17 inline void add(int x,int y,int val)
18 {
19 for(int i=x;i<=maxn;i+=lowbit(i))
20 for(int j=y;j<=maxn;j+=lowbit(j))
21 tree[i][j]+=val;
22 }
23 inline int query(int x,int y)
24 {
25 int ans=0;
26 for(int i=x;i;i-=lowbit(i))
27 for(int j=y;j;j-=lowbit(j))
28 ans+=tree[i][j];
29 return ans;
30 }
31 int main()
32 {
33 int n;
34 for(int k=1;k<=2;k++)
35 {
36 read(n);
37 for(int i=1;i<=n;i++)
38 {
39 int how;
40 read(how);
41 if(how==0)// 减
42 {
43 int x,y,v;read(x);read(y);read(v);
44 add(x,y,-v);
45 }
46 else if(how==1)//jia
47 {
48 int x,y,v;read(x);read(y);read(v);
49 add(x,y,v);
50 }
51 else//sum
52 {
53 int a,b,c,d;
54 read(a);read(b);read(c);read(d);
55 printf("%d\n",query(c,d)+query(a-1,b-1)-query(a-1,d)-query(c,b-1));
56 }
57 }
58 }
59 return 0;
60 }