超级树状数组,就是用树状数组来进行区间修改+区间查询操作的东西,好处是和线段树相比快了不少。
首先先来复习一下普通的树状数组
int tree[MAXN];
int lowbit(int x) {
return x & -x;
}
void update(int x, int d) {
while (x <= n) {
tree[x] += d;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
注意: update
是 $x\sim n$ 都加上 $d$,sum
是求 $x$。
求区间 $l\sim r$ 的问题,我们可以转化为求 $1\sim k$ 的问题,对于这个问题,我们可以定义一个差分数组 $d_i=a_i - a_{i - 1}$ 显然 $a_i=d_1 + d_2 + … + d_i$。
$$\begin{aligned}&a_1+a_2+…+a_i\\=&~~d_1+(d_1+d_2)+(d_1+d_2+d_3)+…+(d_1+d_2+…+d_i)\\=&~~id_1+(i-1)d_2+…+[i-(i-1)]d_i\\=&~~i\sum\limits_{j=1}^i d_j-\sum\limits_{j=1}^i (j-1)d_j\end{aligned}$$
当求第一个数时,我们只需将 $x$ 和 $y+1$ 这两个差分数组更改,其他的差分数组要么没有被修改,要么被抵消掉了,当求第二个数时,我们也是将那两个数更改,其他的和前面的同理,对于这个数,自己推去吧。
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
typedef pair<ll, ll> pll;
inline ll read() {
char ch = getchar(); ll fu = 0, s = 0;
while(!isdigit(ch)) fu |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return fu ? -s : s;
}
const int MAXN = 1e5 + 10;
int n, m, a[MAXN];
struct Node {
ll tree[MAXN];
int lowbit(int x) {
return x & -x;
}
void update(int x, ll d) {
while (x <= n) {
tree[x] += d;
x += lowbit(x);
}
}
ll sum(int x) {
ll ans = 0;
while (x) {
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
} tr1, tr2;
void solve() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
ll t = a[i] - a[i - 1];
tr1.update(i, t);
tr2.update(i, (i - 1) * t);
}
while (m--) {
int op = read(), x = read(), y = read(), k;
if (op == 1) {
k = read();
tr1.update(x, k);
tr1.update(y + 1, -k);
tr2.update(x, (x - 1) * k);
tr2.update(y + 1, -y * k);
} else {
printf("%lld\n", (tr1.sum(y) * y - tr2.sum(y)) - (tr1.sum(x - 1) * (x - 1) - tr2.sum(x - 1)));
}
}
}
signed main() {
int T = 1;
// T = read();
while(T--) solve();
return 0;
}