T4701 【卜卜】树状数组模板

attack

发布于 2018-04-12 11:00:13

6050

发布于 2018-04-12 11:00:13

文章被收录于专栏：数据结构与算法

题目描述

在二维平面内给定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：

说明

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 }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-08-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法