前言
某5机房最最最弱的菜鸡，在gm突击测验树状数组版题的时候，居然忘记了如何打区间修改，区间查询（出生不带脑子名副其实）
然后他抱着疑问的心态打开了自己之前关于树状数组的blog，发现他之前写了个什么玩意
再仔细回想了一下思想发现自己并没有真正理解，于是也就有了为什么暑假学的东东现在还写blog。毕竟学习不求甚解是不可取的（突然讲起了大道理）
题目
给定数列 $a[1],a[2], ldots , a[n] $，你需要依次进行 个操作，操作有两类：
- 1 l r x：给定 (l, r, x)，对于所有 (i /in [l, r])，将 (a[i]) 加上 (x)（换言之，将 $a[l],a[l + 1], ldots , a[r] $ 分别加上 (x)）；
- 2 l r：给定(l, r) ，求(sum_{i = l}^{r} a[i]) 的值（换言之，求(a[l]+a[l + 1]+ ldots + a[r]) 的值）。
思路&&推导过程
在有了前置知识（丝毫不心虚），我们就可以知道，如何单点修改，区间查询和 如何区间修改，单点查询了。
在区间修改，单点查询中知道了我们可以用差分来实现区间修改。而第(i)个数用差分表示应该是(sum[1] + sum[2] +ldots + sum[i])
那么第1个数到第(i)个数， 该如何用一串差分表示呢？
((sum[1]) + (sum[1] + sum[2]) + ldots + (sum[1] + sum[2] +ldots + sum[i]))
于是乎，用笔者那本就不存在的脑子想了一想：
我们就枚举每一个数再求(sum)不香吗？但笔者立马否定了这个想法，毕竟(O(n imes n imes log_{n}))真的很惊悚。。。
我们再回到这个式子
((sum[1]) + (sum[1] + sum[2]) + ldots + (sum[1] + sum[2] +ldots + sum[i]))
(= sum[1] * i + sum[2] * (i - 1) + ldots + sum[i] * (i - i + 1))
(= (sum[1] + sum[2] +ldots + sum[i]) imes i - ((sum[1] imes (1 - 1) + (sum[1] imes (1 - 1) + ldots + sum[i] imes (i - 1))
于是大师我悟了！:
((sum[1] + sum[2] +ldots + sum[i])) 不就是用区间修改区间查询就可以解决了吗？
而((sum[1] imes (1 - 1) + (sum[1] imes (1 - 1) + ldots + sum[i] imes (i - 1))我们就用另一个(Update)来存就行了
于是代码就很快乐的打出来了！（改改就能用）
AC代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6 + 5;
int n, q;
int a[maxn];
int sum[maxn];
long long BIT[maxn], BIT2[maxn];
int Lowbit(int a){
return a & (-a);
}
void Update(int x, int k){
for(int i = k; i <= n; i += Lowbit(i)){
BIT[i] += x;
}
}
void Update2(int x, int k){
for(int i = k; i <= n; i += Lowbit(i)){
BIT2[i] += (long long)x * (k - 1);
}
}
long long Sum(int x){
long long ans = 0;
for(int i = x; i > 0; i -= Lowbit(i)){
ans += BIT[i];
}
return ans;
}
long long Sum2(int x){
long long ans = 0;
for(int i = x; i > 0; i -= Lowbit(i)){
ans += BIT2[i];
}
return ans;
}
int main() {
scanf("%d %d", &n, &q);
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
sum[i] = a[i] - a[i - 1];
Update(sum[i], i);
Update2(sum[i], i);
}
for(int i = 1; i <= q; i ++){
int flag;
scanf("%d", &flag);
if(flag == 1){
int x, l, r;
scanf("%d %d %d", &l, &r, &x);
Update(x, l);
Update(-x, r + 1);
Update2(x, l);
Update2(-x, r + 1);
}
else{
int l, r;
scanf("%d %d", &l, &r);
printf("%lld
", (r * Sum(r) - Sum2(r)) - ((l - 1) * Sum(l - 1) - Sum2(l - 1)));
}
}
return 0;
}