超级树状数组

标签：typedef ch 树状 int 超级 数组 include

超级树状数组，就是用树状数组来进行区间修改+区间查询操作的东西，好处是和线段树相比快了不少。

例题

首先先来复习一下普通的树状数组

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 是求 \(1\sim 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;
}

标签：typedef,ch,树状,int,超级,数组,include
From： https://www.cnblogs.com/wh2011/p/18646187