P3368 【模板】树状数组 2
题目描述
给定一个长度为 n 的整数数列 a1,a2,…,an,你需要依次处理 m 次操作。操作共有下面两种:
∙将数列中某一个区间内的每一个数都加上一个给定的整数;
∙求出数列中某一个数的值。
输入格式
第一行输入两个整数 n,m(1≦n,m≦5×105) 分别代表数列的长度和操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{30} \leqq a_i \leqq 2^{30}\right)$ 代表数列的初始值。
此后 m 行,每行先输入一个整数 op(1≦op≦2) 代表操作类型,随后在同一行继续输入:
∙若 op=1,输入三个整数 $x, y, k \left(1 \leqq x \leqq y \leqq n;\ -2^{31} \leqq k \leqq 2^{31}\right)$,表示将区间 [x,y] 内的每个数都加上 k;
∙若 op=2,输入一个整数 x(1≦x≦n),表示询问第 x 个数的值。
保证在任意时刻,数列中任意一个数的绝对值都不大于 230。
输出格式
对于每次 op=2 的操作,新起一行输出一个整数,代表第 x 个数当前的值。
测试样例
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
6
10
样例 1 解释
数列的初始值为 {1,5,4,2,3}。
∙操作 "1 2 4 2":将区间 [2,4] 内的每个数加上 2,数列变为 {1,7,6,4,3};
∙操作 "2 3":第 3 个数当前为 6;
∙操作 "1 1 5 -1":将区间 [1,5] 内的每个数加上 −1,数列变为 {0,6,5,3,2};
∙操作 "1 3 5 7":将区间 [3,5] 内的每个数加上 7,数列变为 {0,6,12,10,9};
∙操作 "2 4":第 4 个数当前为 10。
因此依次输出 6 和 10。
6 7
1 -2 3 0 4 6
1 1 3 5
2 2
1 2 4 -1
2 6
1 3 6 2
2 2
2 6
3
6
2
8
样例 2 解释
数列的初始值为 {1,−2,3,0,4,6}。
∙操作 "1 1 3 5":将区间 [1,3] 内的每个数加上 5,数列变为 {6,3,8,0,4,6};
∙操作 "2 2":第 2 个数当前为 3;
∙操作 "1 2 4 -1":将区间 [2,4] 内的每个数加上 −1,数列变为 {6,2,7,−1,4,6};
∙操作 "2 6":第 6 个数当前为 6;
∙操作 "1 3 6 2":将区间 [3,6] 内的每个数加上 2,数列变为 {6,2,9,1,6,8};
∙操作 "2 2":第 2 个数当前为 2;
∙操作 "2 6":第 6 个数当前为 8。
因此依次输出 3,6,2,8。
提示
本题的数据分为以下三档:
∙对于 30% 的数据,1≦n≦8,1≦m≦10;
∙对于 70% 的数据,1≦n,m≦104;
∙对于 100% 的数据,1≦n,m≦5×105。