树状数组（Fenwick Tree）是处理区间查询和单点更新的高效数据结构，时间复杂度为 O(log n)。本文通过对比前缀和与树状数组的差异，详细解析 lowbit 操作、update 及 getprefix 函数的实现原理。结合蓝桥杯经典例题“殷老师排队”与“异或和”，展示了树状数组在动态数组求和及子树异或查询中的具体应用，并提供了 C++ 完整代码实现与复杂度分析。
树状数组（Fenwick Tree）是一种高效的数据结构，主要用于解决区间查询和单点更新问题，时间复杂度均为 O(log n)，适用于数组长度固定且需要频繁进行这两种操作的场景。它是一种可以'动态求区间和'的树形数据结构，但并没有真正构造出边来，所以称为'树状的'。
以下是其核心知识点：
| 操作 | 前缀和 | 树状数组 |
|---|---|---|
| 初始化 | O(n) | O(n log n) 或 O(n) |
| 单点修改 | O(n) | O(log n) |
| 区间查询 | O(1) | O(log n) |
| 区间修改 | O(n) (需配合差分) | O(log n) |
lowbit 是一种位运算操作，用于计算出数字的二进制表达中的最低位的 1 以及后面所有的 0。
int lowbit(int x) { return x & -x; } // O(1)
解释：x = 6 → 二进制 0000 0110；~x + 1 = -x → 二进制 1111 1010；x & (-x) → 二进制 0000 0010 → 十进制 2。
lowbit(x) 的值等于 2^k，其中 k 是 x 的二进制末尾连续 0 的个数。
定义 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
如何进行单点修改？ 假设要修改 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()！
// 给 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
}
// 返回区间 [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;
}
体育课上，殷老师正在给学生们排队，排完队后他发现这些学生有些不同。每个学生都有一个魅力值 ai 和愉悦值 bi，愉悦值的计算公式如下： bi = (i-1)ai - sum(a[1]...a[i-1]) + sum(a[i+1]...an) - (n-i)ai 作为一名优秀的教师他一眼就可以看出学生们的魅力值，但随着时间的推移魅力值可能会发生变化，所以愉悦值也会发生变化。在排队的过程中会有 n 个事件，这 n 个事件共分为两种情况：
第一行包含两个整数 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;
}
给一棵含有 n 个结点的有根树，根结点为 1，编号为 i 的点有点权 ai（i∈[1,n]）。现在有两种操作，格式如下：
输入的第一行包含两个正整数 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：更加直观
// 需要设置两个数组：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;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online