d799: 区间求和
Tags : 线段树
Accepted rate : 274人/350人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-10-03 20:29

Content

在本题描述之前,首先衷心感谢morris1028为线段树的高级数据结构算法打开了大门!

给你N个数据,不断地改变这N个数据的同时也不停地问你某个区间中所有元素的和!

Input

只有一笔测试数据。

第一行是N(0<N<=500000),接下来有N个数a[i][j](0<=a[i,j]<=32767)。

然后是一个数字Q(0<Q<=500000),接下来有Q组要求和询问。

每组要求或询问的格式是:首先是一个数 v (v=1或2),

若v=1则表示是要求,接下来有三个数据 x y k (0<x<=y<=N且0<=k<=1000),表示从第x个数据至第y个数据每个都加上k;

若v=2则表示是询问,接下来有两个数据 x y (0<x<=y<=N),你得输出从第x个数据至第y个数据的所有元素的和。

Output

如果是要求,则不用输出;

如果是询问,则输出所要求的元素之和。

Sample Input #1
4
1 2 3 4
5
2 1 3
1 1 3 1
2 1 3
1 1 4 1
2 1 4
Sample Output #1
6
9
17
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <50M
Hint :

32767×500000>2147483647

Tags:
线段树
出處:
[管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
22705 d799
解法
906 2020-09-27 15:13