树状数组进阶

权值树状数组

介绍

用权值，而非下标来维护树状数组，用来解决计数问题。

• 树状数组 $t_i$ 维护权值为 $a_i$ 元素的个数
• 通常配合离散化

操作

• 更新 $t_i$ 即更新 $a_i$ 的计数，即权值为 $a_i$ 的元素个数
• 查询 $t_i$ 即查询 $a_i$ 的计数前缀和，即 $\leq a_i$ 的元素个数

二阶差分扩展

介绍

通过维护两个树状数组，实现单点更新、区间更新、单点查询、区间查询，强度直逼线段树。

• 树状数组 $f$ 维护 $a$ 的差分数组
• 树状数组 $g$ 维护 $j\times f$

但思考起来和写起来都不如线段树直观，没啥用啊，评价给到npc

公式推导

• $sum_a = \sum_{i=1}^n a_i = \sum_{i=1}^n\sum_{j=1}^i f_j$

eg. $sum_a(3) = a_1 + a_2 + a_3 \\= (f_1) + (f_1 + f_2) + (f_1 + f_2 + f_3) \\= f_1 + 2f_2 + 3f_3$

• $sum_a(x) = \sum_{j=1}^x[f_j \times (x - j + 1)] \\= \sum_{j=1}^x[f_j\times(x+1)-f_j\times j] \\= \sum_{j=1}^x(x+1)f_j - \sum_{j=1}^xjf_j$

$\therefore sum_a(x) = (x+1)sum_f(x) - sum_{jf}(x)$

可视化示例

$f_1$	$f_2$	$f_3$	$f_4$	$f_5$
$a_5$
$a_4$
$a_3$
$a_2$
$a_1$
$f_1$	$2f_2$	$3f_3$	$4f_4$	$5f_5$

基础操作

单点更新

同时更新 $f_i$ 和 $g_i$

void update(int x, int k){
    while(x <= n) 
        f[x] += k, 
        g[x] += k * x, 
        x += lowbit(x); 
}

前缀查询

查询 $f$ 和 $g$ 的前缀和

pair<int, int> query(int x){
    int res_f = 0, res_g = 0;
    while(x > 0)
        res_f += f[x], 
        res_g += g[x], 
        x -= lowbit(x);
    return make_pair(res_f, res_g);
}

初始化

vector<int> f, g;
// 依旧 1-based 数组 a
void build(const vector<int> &a){
    f.resize(a.size(), 0);
    g.resize(a.size(), 0);
    update(1, a[1]);
    for(int i = 2;i < a.size();i++)
        update(i, a[i] - a[i-1]);
}

进阶操作

区间修改

和一阶差分扩展一样的思路

void addRange(int l, int r, int k){
    update(l, k);
    if(r + 1 <= n) update(r + 1, -k);
}

单点修改

相当于修改区间 $[l, l]$

void addPoint(int x, int k){
    addRange(x, x, k);
}

单点查询

查询 $a_i$ 的值，直接取 $f_i$

int queryPoint(int x){
    return query(x).first;
}

前缀查询

查询 $i$ 位置的前缀和，按公式计算

int querySum(int x){
    auto [sum_f, sum_g] = query(x);
    return (x + 1) * sum_f - sum_g;
}

区间查询

查询区间 $[l,r]$ 的和，两个前缀和减一下

int queryRangeSum(int l, int r){
    return querySum(r) - querySum(l-1);
}