P3372 【模板】线段树 1
题目描述
给定一个长度为 n 的数列 {a1,a2,…,an},你需要支持下面两种操作:
∙将某个区间内的每一个数都加上 k;
∙求出某个区间内每一个数的和。
输入格式
第一行输入两个整数 n,m(1≦n,m≦105) 代表数列中的元素数量和操作总次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 2 \times 10^{18}\right)$ 代表数列的初始值。
此后 m 行,第 i 行先输入一个整数 op(1≦op≦2) 代表第 i 次操作的类型:
∙若 op=1,再输入三个整数 $x, y, k \left(1 \leqq x \leqq y \leqq n;\ 1 \leqq k \leqq 2 \times 10^{18}\right)$,表示将区间 [x,y] 内的每个数加上 k;
∙若 op=2,再输入两个整数 x,y(1≦x≦y≦n),表示询问区间 [x,y] 内每个数的和。
保证任意时刻数列中所有数的和不超过 2×1018。
输出格式
按操作顺序,对于每次 op=2 的操作,新起一行输出一个整数,代表该次询问的答案。
测试样例
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
11
8
20
样例 1 解释
初始数列为 {1,5,4,2,3}。
∙第 1 次操作询问 [2,4] 的和,为 5+4+2=11;
∙第 2 次操作将 [2,3] 内的数都加 2,数列变为 {1,7,6,2,3};
∙第 3 次操作询问 [3,4] 的和,为 6+2=8;
∙第 4 次操作将 [1,5] 内的数都加 1,数列变为 {2,8,7,3,4};
∙第 5 次操作询问 [1,4] 的和,为 2+8+7+3=20。
因此依次输出 11,8,20。
6 6
4 7 1 9 3 5
2 1 6
1 2 5 4
2 2 5
1 1 3 6
2 1 3
2 4 6
29
36
38
25
提示
对于 15% 的数据,n≦8,m≦10;
对于 35% 的数据,n≦103,m≦104;
对于 100% 的数据,1≦n,m≦105,ai,k 均为正数,且任意时刻数列中所有数的和不超过 2×1018。