C++ 树状数组算法详解与实战

2. lowbit 和树状数组 t[] 的联系

定义 t[i] 存储以 i 结尾，且区间大小为 lowbit(i) 的区间和。 t[j] = sum(a[j])，其中 j 的范围为 [i-lowbit(i)+1, i]，可将 [i-lowbit(i)+1, i] 称为'管辖区间'。

例子：a[1..n] 分别为 1, 2, 3, 4...n

• t[1] --> 1
• t[2] --> [1, 2]
• t[3] --> 3
• t[4] --> [1, 4]
• t[5] --> 5
• t[6] --> [5, 6]
• t[7] --> 7
• t[8] --> [1, 8]

如何进行单点修改？ 假设要修改 a[3]，包含 a[3] 的区间有 t[3], t[4], t[8]，所以应该修改这 3 个节点。 只需进行 +lowbit 操作即可（二进制性质）：3+lowbit(3)=4，4+lowbit(4)=8......就是原来的编号加上它所管辖的区域等于后面与之相连的编号。

怎么进行区间查询？ 第一步：将其拆为两个区间的差。例如：假设要查询 [3, 7] 的和，就要拆分为 sum[1, 7] - sum[1, 2]。 由上图，我们要求 sum[1, 7]，结果为 t[7] + t[6] + t[4]，通过 lowbit 即可得到：7-lowbit(7)=6，6-lowbit(6)=4。就是原来的编号减去它所管辖的区域等于前面与之相连的编号。 于是可以直接得到树状数组最重要的两个函数 update() 和 getprefix()！

1. update 函数

// 给 a[k] 增加 x
void update(int k, int x) {
    for (int i = k; i <= n; i += lowbit(i)) t[i] += x;
    // 解释：把 a[k] 增加 x，相当于把与 a[k] 相关的几个区间和都要加上 x。所以 t[i] 要加上 x
}

2. getprefix 函数

// 返回区间 [1, k] 的和
int getprefix(int k) {
    int res = 0;
    for (int i = k; i >= 1; i -= lowbit(i)) res += t[i];
    // 以管辖区间为单位依次向前加上 t[i]!!! 就返回的是区间 [1, k] 的和！
    return res;
}

四、例题详解

例题 1：蓝桥杯官网——殷老师排队

问题描述

体育课上，殷老师正在给学生们排队，排完队后他发现这些学生有些不同。每个学生都有一个魅力值 ai 和愉悦值 bi，愉悦值的计算公式如下： bi = (i-1)ai - sum(a[1]...a[i-1]) + sum(a[i+1]...an) - (n-i)ai 作为一名优秀的教师他一眼就可以看出学生们的魅力值，但随着时间的推移魅力值可能会发生变化，所以愉悦值也会发生变化。在排队的过程中会有 n 个事件，这 n 个事件共分为两种情况：

1. 第 x 个学生的魅力值变为 y。
2. 殷老师想查看第 x 个学生的愉悦值。 殷老师太忙了，所以你可以帮他计算某个学生的愉悦值吗？

输入格式

第一行包含两个整数 n, m，表示学生的个数和事件的个数。 第二行包含 n 个数表示每个学生的魅力值。 之后每一个操作的开头都输入一个数字 op 表示事件的类型，如果 op=1 则输入两个整数 x, z 表示将第 x 个学生的魅力值修改为 z；若 op=2 则输入一个整数 x 表示询问从第 x 个学生的愉悦值。

输出格式

对于每个操作 2 输出一个数字 ans 表示学生的愉悦值。

样例输入

10 10
74 56 25 77 55 36 50 89 42 15
1 2 38
2 8
2 1
2 1
3 11
2 1
2 6
2 8
1 5 47
2 3

样例输出

147 -239 -239 -253 -23 161 189

数据规模

对于所有评测数据，1≤n,m≤10^5，1≤op≤2，1≤x≤n，0≤z≤10^9。

代码详解！

方法一：正确方法，树状数组

#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], t[N], n, m;

int lowbit(int x) {
    return x & -x;
}

void update(int k, ll x) // 单点修改，将 a[k] 加上 x
{
    a[k] += x;
    for (int i = k; i <= n; i += lowbit(i)) t[i] += x;
}

ll getprefix(int k) // 求区间 [1, k] 的和
{
    ll res = 0;
    for (int i = k; i >= 1; i -= lowbit(i)) res += t[i];
    return res;
}

ll getsum(int l, int r) // 求区间 [l, r] 的和
{
    return getprefix(r) - getprefix(l - 1);
}

ll b(int i) // 求愉悦值
{
    return (2 * i - n - 1) * a[i] - getsum(1, i - 1) + getsum(i + 1, n);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        update(i, x);
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            ll x, y;
            cin >> x >> y;
            update(x, -a[x] + y); // 将 a[x] 加上 -a[x]+y，即将 a[x] 变成 y
        } else {
            int x;
            cin >> x;
            cout << b(x) << '\n';
        }
    }
    return 0;
}

大家可能会好奇，树状数组的相关操作和前缀和差分具有相似之处。那么这题可以用普通的前缀和和差分方法做吗？其实是可以的。只是时间复杂度较大，只能通过部分案例。

方法二：普通前缀和差分方法，时间复杂度高

#include <iostream>
#include<cstring>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
ll a[N], diff[N], prefix[N], n;

// 求前缀和
void pre_fix() {
    memset(prefix, 0, sizeof(prefix));
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
}

// update(i,k) 将 a[i] 加上 k
void update(int i, int k) {
    diff[i] += k;
    diff[i + 1] -= k; // 前缀和还原
    for (int i = 1; i <= n; i++) a[i] = a[i - 1] + diff[i];
    pre_fix();
}

// 前缀和：求 [1, k] 的和
ll getprefix(int k) {
    return prefix[k];
}

ll getsum(int l, int r) {
    return getprefix(r) - getprefix(l - 1);
}

ll b(int i) {
    return (2 * i - n - 1) * a[i] - getsum(1, i - 1) + getsum(i + 1, n);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 先初始差分数组：
    for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1];
    // 初始前缀和数组
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            update(x, y - a[x]);
        } else if (op == 2) {
            int x;
            cin >> x;
            cout << b(x) << '\n';
        }
    }
    return 0;
}

例题 2：23 年蓝桥杯真题——异或和

问题描述

给一棵含有 n 个结点的有根树，根结点为 1，编号为 i 的点有点权 ai（i∈[1,n]）。现在有两种操作，格式如下：

• 1 x y：该操作表示将点 x 的点权改为 y。
• 2 x：该操作表示查询以结点 x 为根的子树内的所有点的点权的异或和。 现有长度为 m 的操作序列，请对于每个第二类操作给出正确的结果。

输入格式

输入的第一行包含两个正整数 n, m，用一个空格分隔。 第二行包含 n 个整数 a1, a2,…, an，相邻整数之间使用一个空格分隔。 接下来 n−1 行，每行包含两个正整数 ui, vi，表示结点 ui 和 vi 之间有一条边。 接下来 m 行，每行包含一个操作。

输出格式

输出若干行，每行对应一个查询操作的答案。

样例输入

4 4
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2

样例输出

4 5 6

评测用例规模与约定

对于 30% 的评测用例，n, m≤1000； 对于所有评测用例，1≤n, m≤100000，0≤ai, y≤100000，1≤ui, vi, x≤n。

代码详解！

方法一：树状数组

#include <iostream>
#include <vector>
using ll = long long;
using namespace std;
const int N = 1e5 + 9;
ll a[N], t[N], idx[N], dfn[N], sz[N];
vector<int> g[N];
int n, m, tot = 0;

int lowbit(int x) {
    return x & -x;
}

void update(int k, int x) {
    for (int i = k; i <= n; i += lowbit(i)) t[i] ^= x;
}

int query(int k) {
    int res = 0;
    for (int i = k; i > 0; i -= lowbit(i)) res ^= t[i];
    return res;
}

void dfs(int x, int fa) {
    dfn[x] = ++tot;
    idx[dfn[x]] = x;
    sz[x] = 1;
    for (const auto& y : g[x]) {
        if (y == fa) continue;
        dfs(y, x);
        sz[x] += sz[y];
    }
}

int main() {
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) update(dfn[i], a[i]);
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) // 更新 x 为 y
        {
            int x, y;
            cin >> x >> y;
            int val = query(dfn[x]) ^ query(dfn[x] - 1);
            // 在初始状态（未进行任何更新操作时），query(dfn[x]) ^ query(dfn[x] - 1) 等于 a[x]；
            // 但在经过更新操作后，它等于节点 x 当前的最新值
            // val 表示的是 DFS 序中某一点的当前点权值
            // query(dfn[x]) 返回区间 [1, dfn[x]] 的异或和。
            // query(dfn[x]-1) 返回区间 [1, dfn[x]-1] 的异或和。
            // 两者异或后，得到的 val 就是位置 dfn[x] 对应的点权（即节点 x 的当前值）。
            update(dfn[x], val ^ y); // 这一步的意思就是将 dfn[x] 所代表的点权（就是 val）在和 val^y 进行异或运算
            // val^val^y=0^y=y，至此，val 被替换成 y！！！
        }
        else // 求异或和
        {
            int x;
            cin >> x;
            int l = dfn[x], r = dfn[x] + sz[x] - 1;
            int ans = query(r) ^ query(l - 1); // 类似 prefix
            // ans 表示 l 到 r 的异或和
            /* 异或（XOR，符号为 ^）具有以下关键性质：
               交换律：a ^ b = b ^ a
               结合律：(a ^ b) ^ c = (a ^ b) ^ c
               自反性：a ^ a = 0（任何数异或自身为 0）
               单位元：a ^ 0 = a（任何数异或 0 等于自身）*/
            // 定义 prefix[i] 为前 i 个元素的异或和：
            // prefix[i] = a[1] ^ a[2] ^ ... ^ a[i]
            // 则区间 [l, r] 的异或和可表示为：
            // a[l] ^ a[l+1] ^ ... ^ a[r] = prefix[r] ^ prefix[l-1]
            // 前面的 1 到 l-1 部分由交换律 a[i]^a[i]=0，都抵消了
            cout << ans << '\n';
        }
    }
    return 0;
}

方法 2：更加简单直观的方法

////// 方法 2：更加直观
// 需要设置两个数组：in_[N] 和 out[N], in_[i] 表示第 i 个结点的入序，out[i] 表示第 i 个结点的出序
// 对树进行一次 dfs，在进入函数时更新入序，在退出函数时更新出序
// 对于以结点 x 为根结点的子树，其所有子结点的 dfs 序都将位于 [ in_[x], out[x] ] 间
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> edge[N]; // edge[i] 存储第 i 个结点的邻接点
int in_[N], out[N]; // in_[i] 存储第 i 个结点的入序，out[i] 存储第 i 个结点的出序
int weight[N]; // weight[i] 存储的第 i 个结点的值 (原始数据)
int tot = 0; // 记录 dfs 序的变量
int seq[N]; // seq[i] 为 dfs 序中第 i 个结点的权值
int n, m;

void dfs(int u, int father) // 对结点 u 进行 dfs，其父结点为 father
{
    in_[u] = ++tot; // 进入函数，计算入序，tot 先自加
    seq[tot] = weight[u]; // 第 tot 个结点的权值是 weight[u]
    for (const auto& v : edge[u]) // 遍历 u 的邻接点 v
    {
        if (v == father) continue;
        dfs(v, u);
    }
    out[u] = tot; // 退出函数，更新 u 的出序，tot 无需自加
}
/* in_[u]：表示节点 u 在 DFS 遍历中首次被访问的时间戳（即进入节点 u 的时间）。
   这个时间戳是唯一的，并且在整个 DFS 过程中严格递增。
   out[u]：表示节点 u 的所有子树都被遍历完成后，退出节点 u 的时间戳。
   由于 DFS 会递归遍历当前节点的所有子节点，
   因此 out[u] 实际上等于当前节点及其所有子树的节点总数（从 in_[u] 开始的连续区间）。*/
/* 入序（in_）：在递归进入节点 u 时立即记录，确保每个节点的入序唯一且递增。
   出序（out）：在遍历完所有子节点后记录，此时的 tot 值恰好等于当前子树的最后一个节点的入序，
   因此 out[u] 表示子树区间的右端点。*/

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &weight[i]); // 输入 n 个结点的原始值
    for (int i = 1; i < n; i++) // 输入 n-1 条无向边
    {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1, 0); // 从 1 号结点开始进行一次 dfs，求出所有结点的 dfs 序，填写 in_数组和 out 数组
    // 此后我们只按照 dfs 序处理结点，原始的 weight 不再使用
    while (m--) {
        int op, x, y;
        scanf("%d", &op);
        if (op == 1) // 把第 x 个结点的权值改为 y
        {
            scanf("%d%d", &x, &y);
            seq[in_[x]] = y; // 转化为将第 in_[x] 个结点 (dfs 序下) 的权值改为 y
        }
        else if (op == 2) {
            scanf("%d", &x); // 查询以 x 为根的子树的异或和
            int ans = 0;
            for (int i = in_[x]; i <= out[x]; i++) // 转化为求区间 [ in_[x], out[x] ] 的异或和
            {
                ans = ans ^ seq[i];
            }
            printf("%d\n", ans);
            // 注意这里使用的是暴力求前缀和的方式而不是前缀和数组
            // 这是因为本题是一边修改一边查询，前缀和数组无法实现动态修改和查询
            // 如果要提高效率可以使用线段树，可在 O(log n) 时间复杂度内完成查询
            // 但对于本题，暴力求异或和即可通过全部测试点
        }
    }
    return 0;
}