P3368 【模板】树状数组 2 题解

· · 题解

树状数组是一种支持单点修改，区间查询的精巧的数据结构，通常用于维护满足结合律和可差分的运算和信息。又称二叉索引树（Binary Index Tree）、Fenwick Tree。

\color{00cd00}\text{原理介绍}

下面这张图展示了树状数组的原理（来源：OI-Wiki）。

其中 c_x 表示以 x 为右端点，长度为 {\rm lowbit}(x) 的区间的和。

例如，$10$ 在二进制表示下为 $10\underset{\blacktriangle}{\bf1}0$，加粗的就是最低位的 $1$，它的权值是 $2$，因此 $\rm lowbit(10)=2$。 再例如，$24$ 在二进制表示下为 $1\underset{\blacktriangle}{\bf1}000$，最低位的 $1$ 的权值为 $8$，因此 $\rm lowbit(24)=8$。 根据位运算知识，可以得到 `lowbit(x) = x & -x`，其中 `&` 为**按位与**运算。

如果一个数减去自己的 \rm lowbit，得到的数再减去自己的 \rm lowbit，不断重复，最终这个数一定会变成 0。

例如 7(111)\overset{\!-1}{\longrightarrow}6(110)\overset{\!-2}{\longrightarrow}4(100)\overset{\!-4}{\longrightarrow}0。

那么我们要计算 a_{1\dots7} 的和，就只需要求 c_7+c_6+c_4 即可。观察上图，看看是不是这样。

由此我们可以得到查询 a_{1\dots x} 的代码：

int query(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

可以发现，树状数组通过将一段数划分成 O(\log n) 段数的和，从而能够实现高效的查询操作。

如果要求任意一段区间 a_{l\dots r} 的和，可以借助前缀和的思想，用 a_{1\dots r} 的和减去 a_{1\dots l-1} 的和，即 query(r) - query(l-1)。这也说明树状数组可以当成一个支持修改的前缀和来用。

如果要将 a_5 加上一个数 k 该如何处理？观察包含 a_5 的区间，只有 c_5，c_6 和 c_8。那么就只需要将 c_5，c_6 和 c_8 都加上 k 即可。而 6=5+\rm lowbit(5)，8=6+\rm lowbit(6)。也就是说，在树状数组中，一个结点 x 的父亲是 x+{\rm lowbit}(x)。由此我们可以得到将 a_x 加上 k 的代码：

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

显然，修改操作的时间复杂度也为 O(\log n)。

但是在本题中，我们需要实现的是区间修改，单点查询，怎么办？借助差分的思想。定义差分数组 d_i = a_i - a_{i-1}。于是有 a_x = \sum\limits_{i=1}^x d_i。如果要在 a_{l\dots r} 加上 k，只需要让 d_l\gets d_l+k,d_{r+1}\gets d_{r+1}-k。使用树状数组维护这一过程即可。

\color{00cd00}\text{代码实现}

树状数组的模板部分和 P3374 是完全一样的。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct BIT{ //树状数组维护差分数组
    int c[N], lowbit(int x){return x & -x;}
    void update(int x, int k){while(x < N) c[x] += k, x += lowbit(x);}
    int query(int x){int s = 0; while(x) s += c[x], x -= lowbit(x); return s;}
} t;
int n, m, a[N];
signed main(){
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i], t.update(i, a[i] - a[i-1]);
    while(m --> 0){
        int op, x, y, k; cin >> op;
        if(op == 1) cin >> x >> y >> k, t.update(x, k), t.update(y + 1, -k);
        if(op == 2) cin >> x, cout << t.query(x) << "\n";
    }
    return 0;
}

推荐继续阅读我的 树状数组小记，包含更多树状数组的高级应用。