C++ 算法竞赛：树状数组与线段树详解及实战
面对频繁的单点修改与区间求和问题，传统前缀和方法在数据更新时会超时。本文将深入解析 C++ 中高效的树状数组与线段树，对比其底层逻辑与性能表现，并提供可直接运行的标准代码模板及典型应用场景。
树状数组（BIT）
树状数组是一种利用二进制特性来高效维护前缀和的数据结构，它在单点修改和前缀查询操作上的时间复杂度均为 O(log n)，且常数极小，空间占用少。
第1步：理解树状数组的结构与 lowbit 运算
树状数组的核心在于如何快速定位父节点和子节点，这依赖于 lowbit(x) 函数。它返回整数 x 在二进制表示下最低位的 1 所对应的值（即最后一个 1 及其后的 0）。
lowbit(x) = x & (-x)
例如，若 x = 6 (二进制 0110)，则 lowbit(6) = 2 (二进制 0010)。这个运算使得我们可以快速找到区间覆盖关系。
第2步：实现核心操作 add 与 query
树状数组通常用数组 tr[] 存储，tr[i] 代表原数组中一段区间的和。具体范围由 i - lowbit(i) + 1 到 i 决定。
- add(x, v)：将位置 x 的值增加 v。因为修改一个元素会影响包含它的所有区间和，所以需要沿着父节点路径向上更新。路径为
x -> x + lowbit(x) -> ...。 - query(x)：计算前缀 [1, x] 的和。通过将区间分解为树状数组中若干个节点的和来计算。路径为
x -> x - lowbit(x) -> ...。
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}第3步：完整应用——动态求连续区间和
题目要求在数列上进行两种操作：
1. 修改某个元素的值。
2. 查询某段子数列 [a, b] 的连续和。
如果直接使用普通前缀和，每次修改元素后需要重新计算后续所有前缀和，时间复杂度为 O(n)，在大规模数据下会超时。而树状数组可以在 O(log n) 时间内完成这两类操作。
注意：树状数组通常基于 1-based 索引，因此在读取输入和处理时需确保索引正确。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N]; // tr[N] 用于存储树状数组状态
int lowbit(int x)
{
return x & -x;
}
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d%d", &n, &m);
// 初始化：先将所有初始值加入树状数组
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
add(i, a[i]);
}
while (m -- )
{
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if (k == 0) // 查询区间 [x, y] 的和
printf("%d\n", query(y) - query(x - 1));
else add(x, y); // 将第 x 个数加上 y（注意题目语义是加值而非赋值，若为赋值需先减旧值）
}
return 0;
}
第4步：树状数组与普通前缀和的选择
普通前缀和是离线算法，支持 O(1) 查询但不支持动态修改（修改代价高）；树状数组是在线算法，支持动态修改且查询效率高。当数据静态不变时首选前缀和；当涉及频繁的混合修改与查询时，树状数组是更优解。
第5步：进阶应用——统计左下方点数（二维偏序简化版）
例题：“数星星”。给定 N 个点的坐标，定义每个点的等级为其左下方（含正左、正下）的点的数目。输出各级别点的数量。
由于输入数据已经按 y 坐标递增、y 相同按 x 递增排序，因此我们只需考虑 x 坐标。当前点输入的之前所有点，其 y 坐标一定小于等于当前点 y 坐标。因此，问题转化为：查询当前点 x 坐标之前有多少个点已经被插入过。这正是树状数组擅长的单点插入与前缀查询。
算法流程： 1. 依次读入每个点的 x, y。
2. 实时查询当前 x 之前的总点数：level[sum(x)]++。
3. 将当前 x 插入树状数组：add(x)。
4. 最后输出 level[0]` 到 `level[n-1] 的统计结果。
#include <bits/stdc++.h>
using namespace std;
const int N = 32010;
int n;
int tr[N], level[N]; // level 记录各等级的星星数量
int lowbit(int x)
{
return x & -x;
}
// 注意这里 add 默认加 1
void add(int x)
{
for (int i = x; i < N; i += lowbit(i)) tr[i] ++ ;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int x, y;
scanf("%d%d", &x, &y);
x ++ ; // 树状数组要求坐标从 1 开始，防止 lowbit(0) 死循环
level[sum(x)] ++ ; // 统计当前等级
add(x); // 插入该 x 坐标
}
for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);
return 0;
}
线段树（Segment Tree）
线段树是基于分治思想的二叉树结构，每个节点表示一个区间。它可以灵活地处理区间查询与区间/单点修改，不仅限于求和，还可以用于求最大值、最小值等。
第1步：基础操作 pushup 与 build
线段树通常使用结构体或数组存储，数组大小一般开 4N 以容纳所有节点。
- pushup(u)：由子节点信息更新父节点。例如求和时，
tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum。 - build(u, l, r)：递归构建线段树。叶子节点
(l==r)直接赋值，内部节点先递归左右子树，再调用pushup。
struct Node
{
int l, r;//左右端点区域
int sum;//存储区间和
}tr[N * 4]; // 空间至少开 4N
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}第2步：单点修改 modify/change
单点修改是指改变区间内某个特定位置的值。递归找到叶子节点进行修改，回溯过程中通过 pushup 更新经过的父节点信息。
void change(int u, int x, int v)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u].sum += v; // 题目需求是加法修改
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid) change(u << 1, x, v);
else change(u << 1 | 1, x, v);
pushup(u);
}
}第3步：区间查询 query
查询区间 [l, r] 的信息。若当前节点区间完全包含在目标区间内，直接返回值；否则根据中点 mid 判断递归方向。需注意，如果查询范围跨越了中点，则需要分别查询左右子树并合并结果（如求和需相加，求 max 需取较大值）。
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) return query(u << 1, l, r); // 完全在左子树
else if(l > mid) return query(u << 1 | 1, l, r); // 完全在右子树
else
{
// 跨越中点，需合并结果
int left = query(u << 1, l, r);
int right = query(u << 1 | 1, l, r);
return left + right;
}
}
}第4步：实战演练——动态求连续区间和完整版
结合以上组件，以下是完整的单点修改区间求和代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int w[N];
struct Node
{
int l, r;
int sum;
}tr[N * 4];
void pushup(int u){ tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; }
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, w[r]};
else
{
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void change(int u, int x, int v)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u].sum += v;
}
else
{
int mid = (tr[u].l + tr[u].r) >> 1;
if(x <= mid) change(u << 1, x, v);
else change(u << 1 | 1, x, v);
pushup(u);
}
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) return query(u << 1, l, r);
if(l > mid) return query(u << 1 | 1, l, r);
return query(u << 1, l, r) + query(u << 1 | 1, l, r);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> w[i];
build(1, 1, n);
while(m --)
{
int op, l, r;
cin >> op >> l >> r;
if(op == 0) cout << query(1, l, r) << endl;
else change(1, l, r);
}
return 0;
}第5步：变式——数列区间最大值
仅需修改结构体中的存储变量名（如改为 maxv）以及 pushup 逻辑。此时 pushup 不再求和，而是取子节点的最大值。query 中的合并逻辑也相应改为取最大值。
struct Node
{
int l, r;
int maxv;
}tr[4 * N];
// 仅展示关键变化
int pushup(Node &t, int l, int r)
{
return t.maxv = max(tr[l].maxv, tr[r].maxv);
}
// 查询时取 max
if(r <= mid) maxv = query(u << 1, l, r);
else if(l > mid) maxv = query(u << 1 | 1, l, r);
else maxv = max(query(u << 1, l, r), query(u << 1 | 1, l, r));
以上就是 C++ 语言中关于树状数组与线段树的详细内容，更多关于 C++ 数据结构优化的资料请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
