首页 > > 程序设计 > C/C++ >

T4701 【卜卜】树状数组模板

2018-06-17 22:02:48来源：未知阅读 ()

题目背景

令夜色的钟声响起

令黄昏（起始）的钟声响起

我爱（渴望）的就只有你

我爱（渴望）你

正因如此独自安静地哭泣吧

正因如此无论你在何处哭泣我都会率先去迎接你

不存在何处直至深夜（小小的你）

你存在此处至美者（心显崇高之人）

在这个夜晚（场所）你（我）是孤独的（一个人）

许下约定送上我的歌

那阵旋律是心灵的奏鸣（撼动）泪珠的音色（舞动）

那阵旋律是心灵的刻划（震动）泪珠的赞歌（庆典）

因为那是令世界湿濡冰冷（心爱）之夜的一滴（歌曲）

那是令世界湿濡亲爱的夜之拥抱（歌曲）

让夜色的吟唱（誓言）来到你身边

让夜色的祝福（誓言）来到你身边绵延（长久）地、永久（长久）地、直到永远

被遗忘的孩子啊

就算全世界（每个人）都遗忘了你我也绝对不会遗忘你

来吧呱呱坠地的孩子啊

回到似睡非睡（摇篮）之中吧

似睡非睡（摇篮）的时间因为约定的钟声而宣告终止

接着我会──

接着你会

黄昏的创始之女（夏娃）你在黎明时微笑

题目描述

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