树状数组 3 ：区间修改，区间查询

【题目描述】

这是一道模板题。

给定数列 a[1],a[2],…,a[n]，你需要依次进行q个操作，操作有两类：

1lrx：给定 l,r,x对于所有 i∈[l,r]，将a[i]加上x（换言之，将 a[l],a[l+1],…a[r] 分别加上 x）；

2lr：给定 l,r求 ∑ri=la[i]的值（换言之，求 a[l]+a[l+1]+⋯+a[r] 的值）。

【输入格式】

第一行包含 2 个正整数 n,q表示数列长度和询问个数。保证 1≤n,q≤1000000。

第二行 n 个整数 a[1],a[2],…a[n]，表示初始数列。保证 |a[i]|≤1000000。

接下来 q 行，每行一个操作，为以下两种之一：

1lrx：对于所有 i∈[l,r]将 a[i] 加上 x；

2lr：输出 ∑ri=la[i]的值。

保证 1≤l≤r≤n,|x|≤1000000。

【输出格式】

对于每个 2lr 操作，输出一行，每行有一个整数，表示所求的结果。

样例

【输入】

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

【输出】

15
34
32
33
50

数据范围与提示

对于所有数据，1≤n,q≤1000000,|a[i]|≤1000000,1≤l≤r≤n,|x|≤1000000。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e6 + 7;
long long n, q, a[maxn],  t[maxn], t1[maxn];long long lowbit(int x) {return x & (-x);
}void change(int x, long long y) {for (int i = x; i <= n; i += lowbit(i)) {t[i] += y;t1[i] += y * x;}
}long long ans(int x) {long long ans = 0;for (int i = x; i; i -= lowbit(i)) {ans += (x + 1) * t[i] - t1[i];}return ans;
}int main() {scanf("%lld%lld", &n, &q);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);change(i, a[i] - a[i - 1]);}for (int i = 1; i <= q; i++) {long long k, l, r, x;scanf("%lld%lld%lld", &k, &l, &r);if (k == 1) {scanf("%lld", &x);change(l, x);change(r + 1, -x);} else {printf("%lld\n", ans(r) - ans(l - 1));}}return 0;
}