【无标题】

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

1. C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
2. Q l r，表示询问数列中第 l∼r 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

1≤N,M≤105,
|d|≤10000,
|A[i]|≤109

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例：

4
55
9
15

树状数组维护区间加减区间求和的板子
设原前缀和数组是 sum[i]
一个树状数组 c0 维护与上一道题一样的数组 b[i] ，另一个树状数组 c1 维护 b[i]∗i
那么修改后第x个数的前缀和就是
sum[x]+(x−1)∗∑i=1xb[i]−∑i=1xb[i]∗i

即
sum[x]+(x−1)∗ask(c0,x)−ask(c1,x)
证明：
修改后第 x 个数的前缀和增加了
∑i=1x∑j=1ib[j]

=∑i=1x(x−i+1)∗b[i]

=(x+1)∑i=1xb[i]−∑i=1xi∗b[i]
 

维护第二个树状数组时，出现了一个令人困惑的点：
假设有一个操作C l r d，在维护第二个树状数组时只需要把位置 l 上的数加上 l∗d，位置 r+1 上的数减去 (r+1)∗d 就可以了。
当时我无法理解这样做的原因
但是我终于知道了
因为 c1 ，它根本就不是一个差分数组。
每次区间修改时，b[i]数组中只有 b[l] 和 b[r+1]发生改变，变化量分别为 +d, −d
故 b[i]∗i 数组中也只有 b[l]∗l 和 b[r+1]∗(r+1) 发生了变化，变化量分别为 d∗l，−d∗(r+1)
我们要的，只不过是 b[i]∗i 这个数组的前缀和而已
根本就不用在意前后是否抵消嘛！

最后

以上就是动听皮卡丘为你收集整理的【无标题】的全部内容，希望文章能够帮你解决【无标题】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。