6695: 树状数组 3 ：区间修改，区间查询
[Creator : ]
Description
这是一道模板题。
给定数列 $a_1,a_2,...,a_n$，你需要依次进行 $q$ 个操作，操作有两类：
位置 $p$ 的前缀和 = $\sum_{i=1}^p {a[i]}=\sum_{i=1}^p \sum_{j=1}^i {d[j]}$，在等式最右侧的式子中 $\sum_{i=1}^p \sum_{j=1}^i {d[j]}$ 中，$d[1]$ 使用了 $p$ 次，$d[2]$ 使用了 $p-1$ 次，$\cdots$。这样我们可以得到：
位置 $p$ 的前缀和 = $\sum_{i=1}^p \sum_{j=1}^i {d[j]} = \sum_{i=1}^{p} d[i] * (p-i+1)=(p+1)*\sum_{i=1}^p d[i] - \sum_{i=1}^p d[i]*i$。
这样，我们可以维护两个数组的前缀和：
区间 $[l,r]$ 的和是：位置 $r$ 的前缀和 - 位置 $l$ 的前缀和。
对于 $sum_2$ 数组的修改也是类似，我们给 $sum_2[i]$ 加上 $l*x$，给 $sum_2[r+1]$ 减去 $(r+1)*x$。
给定数列 $a_1,a_2,...,a_n$，你需要依次进行 $q$ 个操作，操作有两类：
- 1 l r x：给定 $l,r,,x$，对于所有 $i \in [l,r]$，将 $a_i$ 加上 $x$（换言之，将 $a_l,a_{l+1},...,a_r$ 分别加上 $x$）；
- 2 l r：给定 $l,r$，求 $\sum_{i=1}^{r}a_i$ 的值（换言之，求 $a_l+a_{l+1}+...+a_r$ 的值）。
说明
基于树状数组 2 的“差分”思路，考虑一下如何在该构建的树状数组中求前缀和：位置 $p$ 的前缀和 = $\sum_{i=1}^p {a[i]}=\sum_{i=1}^p \sum_{j=1}^i {d[j]}$，在等式最右侧的式子中 $\sum_{i=1}^p \sum_{j=1}^i {d[j]}$ 中，$d[1]$ 使用了 $p$ 次，$d[2]$ 使用了 $p-1$ 次，$\cdots$。这样我们可以得到：
位置 $p$ 的前缀和 = $\sum_{i=1}^p \sum_{j=1}^i {d[j]} = \sum_{i=1}^{p} d[i] * (p-i+1)=(p+1)*\sum_{i=1}^p d[i] - \sum_{i=1}^p d[i]*i$。
这样，我们可以维护两个数组的前缀和：
- 一个数组是 $sum_1[i] = d[i]$；
- 一个数组是 $sum_2[i] = d[i]*i$。
查询
位置 $p$ 的前缀和是：$(p+1)*sum_1$ 数组中的 $p$ 的前缀和 - $sum_2$ 数组中的 $p$ 的前缀和。区间 $[l,r]$ 的和是：位置 $r$ 的前缀和 - 位置 $l$ 的前缀和。
修改
对于 $sum_1$ 数组的修改问题等同于问题 2 中对 $d$ 数组修改。对于 $sum_2$ 数组的修改也是类似，我们给 $sum_2[i]$ 加上 $l*x$，给 $sum_2[r+1]$ 减去 $(r+1)*x$。
Input
第一行包含 $2$ 个正整数 $n,q$，表示数列长度和询问个数。保证 $1 \leq n,q \leq 10^6$。
第二行 $n$ 个整数 $a_1,a_2,...,a_n$，表示初始数列。保证 $|a_i| \leq 10^6$。
接下来 $q$ 行，每行一个操作，为以下两种之一：
第二行 $n$ 个整数 $a_1,a_2,...,a_n$，表示初始数列。保证 $|a_i| \leq 10^6$。
接下来 $q$ 行，每行一个操作，为以下两种之一：
- 1 l r x：给定 $l,r,,x$，对于所有 $i \in [l,r]$，将 $a_i$ 加上 $x$；
- 2 l r：给定 $l,r$，求 $\sum_{i=1}^{r}a_i$ 的值。
Output
对于每个 2 l r 操作，输出一行，每行有一个整数，表示所求的结果。
Sample 1 Input
5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4
Sample 1 Output
15
34
32
33
50