树状数组

简介

写起来以及跑起来非常快的数据结构

实现原理其实也挺简单，树状数组中的每个点i都存了以这个点为右端点的原序列的一段区间

点i的区间长度为 $2^{i的末尾零的个数}$

举个例子，点10100存的数据为10100 10101 10110 10111

树状数组上二分

模板

int query() {
    int l = 0, r = n + 1, mid, sum = 0, ans = 0; // (l, r) 左开右开, Log[i] 表示小于 i 的 2 的最大次幂
    while (l + 1 < r) {
        mid = l + Log[r - l];
        if (sum + Bit[mid] < mid) r = mid;
        else sum += Bit[mid], ans = l = mid;
    } return ans;
}

高阶前缀和

众所周知，树状数组是用来维护单点加，求若干阶前缀和的

举个例子，单点加，区间求和就是求一阶前缀和，而区间加，区间求和就是求二阶前缀和

这里我们来推一下单点加，求二阶前缀和的式子

令 $a$ 为原数组，$s$ 为其二阶前缀和

$s_k=\sum_{i=1}^k\sum_{j=1}^ia_j=\sum_{i=1}^ka_i\sum_{j=i}^k=\sum_{i=1}^k(n-i+1)a_i=(n+1)\sum_{i=1}^ka_i-\sum_{i=1}^kia_i$​

所以我们拿两个树状数组分别维护 $a_i$ 和 $ia_i$​ 的前缀和即可

二维前缀和一般用于解决区间加，区间求和的情况

struct Fenwick {
    ll B1[maxn], B2[maxn];
    void add(int x, int v) {
        for (int i = x; i <= n; i += lowbit(i))
            B1[i] += v, B2[i] += x * v;
    }

    ll get_sum(int x) {
        ll s = 0;
        for (int i = x; i; i -= lowbit(i))
            s += (x + 1) * B1[i], s -= B2[i];
        return s; 
    }

    void update(int l, int r, int v) { add(l, v); add(r + 1, -v); }

    ll query(int l, int r) { return get_sum(r) - get_sum(l - 1); } 
} Bit;

我们再来看一下三阶前缀和

$s_k=\sum_{i=1}^k\sum_{j=1}^i\sum_{d=1}^ja_d=\sum_{i=1}^ka_i\sum_{j=i}^k\sum_{d=j}^k=\sum_{i=1}^k\frac{(k-i+1)(k-i+2)}{2}a_i=\frac{(k+1)(k+2)}{2}\sum_{i=1}^ka_i-\frac{2k+3}{2}\sum_{i=1}^kia_i+\frac{1}{2}\sum_{i=1}^ki^2a_i$

所以我们只需要用三个树状数组维护 $a_i$、$ia_i$ 以及 $i^2a_i$ 的前缀和即可

struct Fenwick {
    ll B1[maxn], B2[maxn], B3[maxn]; int n;
    void init(int _n) { n = _n; }
    
    void add(int x, ll v) {
        for (int i = x; i <= n; i += lowbit(i))
            B1[i] += v, B2[i] += v * x, B3[i] += v * x * x;
    }

    ll get_sum(int x) {
        ll s = 0;
        for (int i = x; i; i -= lowbit(i))
            s += B1[i] * (x + 1) * (x + 2) - B2[i] * (2 * x + 3) + B3[i];
        return s / 2;
    }

    void update(int l, int r, int v) { add(l, v); add(r + 1, -v); }

    ll query(int l, int r) { return get_sum(r) - get_sum(l - 1); } 
} Bit;