超级树状数组

残阳如血

2024-05-25 16:09:58

Algo. & Theory

众所周知：

所以，能不能实现一个可以区间修改、区间查询的树状数组呢？

由于涉及区间操作，考虑差分数组 \{d_n\}。

区间修改

对于原数组 [l,r] 区间每个数加 w。

可以转化为两次单点修改，即 l 单点处加 +w，r+1 单点处加 -w。

区间查询

对于原数组 [l,r] 区间求和。

显然 \sum\limits_{i=l}^r a_i 可以差分为两个 [1,u] 的前缀求和。

\sum\limits_{i=1}^{u} a_i =\sum\limits_{i=1}^u\sum\limits_{j=1}^{i}d_j

观察每一个 a_i=\sum\limits_{j=1}^{i}d_j，可以发现

\begin{aligned} a_1&=d_1\\ a_2&=d_1+d_2\\ a_3&=d_1+d_2+d_3\\ \cdots\\ a_u&=d_1+d_2+d_3+\cdots+d_u \end{aligned}

所以 d_1 的贡献为 u，d_2 的贡献为 u-1，d_3 的贡献为 u-2，……，d_u 的贡献为 1。

故可得 d_k 的贡献为 u-j+1。

\sum\limits_{i=1}^u\sum\limits_{j=1}^{i}d_j=\sum\limits_{j=1}^{u}d_j(u-j+1)

发现 u+1 的值是固定的，可以提取出来：

\sum\limits_{j=1}^{u}d_j(u-j+1)=\Big((u+1)\sum\limits_{j=1}^{u}d_j\Big)-\Big(\sum\limits_{j=1}^{u}(j\times d_j)\Big)

因此同时使用两个树状数组维护 \{d_n\}、\{n\times d_n\} 即可，该技巧即为超级树状数组。

代码实现

typedef long long lint;
lint sum(int p, lint *t) { // 查询 t 中 [1,p] 之和
    lint res = 0;
    for (int i = p; i; i -= lowbit(i))
        res += t[i];
    return res;
}

lint ask(int p) {
    return sum(p, d) * (p + 1) - sum(p, f);
}

lint query(int l, int r) {
    return ask(r) - ask(l - 1);
}

void add(int p, lint x, lint *t) {
    for (int i = p; i <= n; i += lowbit(i)) t[i] += x;
}

void update(int l, int r, lint x) {
    add(l, x, d), add(r + 1, -x, d);
    add(l, x * l, f);
    add(r + 1, -x * (r + 1), f);
}