树状数组（BIT）与线段树详解
在算法中，区间查询（如求区间和、最大值）和单点 / 区间修改是高频问题。传统方法（如前缀和数组）在修改时时间复杂度为 O (n)，无法满足大规模数据需求。树状数组（Binary Indexed Tree, BIT）和线段树（Segment Tree）通过 “分层管理区间” 的思想，将两种操作的时间复杂度均优化至 O (logn)，成为解决此类问题的核心工具。
一、树状数组（BIT）：轻量级区间工具
树状数组是一种实现简单、常数小的数据结构，核心解决 “单点修改 + 区间查询” 问题，也可通过差分扩展到 “区间修改 + 单点查询”。其本质是用数组模拟 “树状分层”，每个节点管理特定范围的区间。
1.1 核心原理：lowbit 操作
树状数组的分层逻辑依赖于二进制的最低位 1，即 lowbit(x) = x & (-x)。该操作的作用是：
找到 x 的二进制表示中最右边的 1（如 x=6=110，lowbit (6)=2=10）；
决定节点 x 的 “管辖范围”（节点 x 管理
[x-lowbit(x)+1, x]的区间）。
lowbit 计算过程
1.2 树状数组结构：分层管辖区间
假设原始数组大小为 8，树状数组（记为 tree）的节点管辖范围如下，每个节点通过 “父 - 子” 关系关联，形成分层管理结构：
1.3 关键操作实现（结合代码）
树状数组的核心操作只有两个：单点修改（insert）和前缀和查询（getSum），区间查询可通过前缀和相减实现。
1.3.1 单点修改：更新某个位置的值
功能：将位置 t的值增加 d。
逻辑：从 t出发，沿 “父节点”（t += lowbit(t)）向上更新所有包含 t的节点 —— 因为这些节点的管辖范围覆盖 t，需同步更新其存储的区间信息。
代码实现：
// 返回x的最低位1
int lowbit(const int x) {
return x & (-x);
}
// 单点修改：将位置t上的值增加d
void insert(int t, int d) {
while (t <= n) { // n为数组大小，避免越界
a\[t] += d; // 更新当前节点的区间信息
t += lowbit(t); // 跳转到父节点（管辖范围更大的节点）
}
}
单点修改流程（t=3，d=1）
1.3.2 前缀和查询：求 [1, t] 的和
功能：计算从第 1 个元素到第 t个元素的累加和。
逻辑：从 t出发，沿 “子节点”（t -= lowbit(t)）向下累加所有管辖范围包含在 [1,t] 内的节点 —— 这些节点的管辖范围无重叠且完整覆盖 [1,t]，累加结果即为前缀和。
代码实现：
// 查询前缀和：计算\[1,t]的和
ll getSum(int t) {
ll sum = 0;
while (t > 0) {
sum += a\[t]; // 累加当前节点的管辖范围和
t -= lowbit(t); // 跳转到子节点（管辖范围更小的节点）
}
return sum;
}
前缀和查询流程（t=6）
1.3.3 区间查询：求 [x, y] 的和
通过前缀和相减实现：
区间和 = getSum(y) - getSum(x-1)
例如，查询 [3,6] 的和 = getSum (6) - getSum (2)，本质是用 “[1,6] 的和” 减去 “[1,2] 的和”，得到目标区间的结果。
1.4 扩展应用：区间修改 + 单点查询
通过差分思想，树状数组可支持 “区间修改”（如给 [L,R] 的所有元素加 val）：
构造差分数组
diff，满足diff[L] += val，diff[R+1] -= val—— 差分数组的前缀和等于原始数组的元素值；用树状数组维护
diff的前缀和；单点查询
a[x]等价于查询diff的前缀和（即getSum(x)），区间修改则转化为对diff的两个单点修改。
1.5 树状数组优缺点
二、线段树：通用区间问题解决方案
线段树是一种功能更强大的树形数据结构，支持 “单点修改、区间修改、区间求和 / 最大值 / 最小值” 等几乎所有区间操作。其核心是将数组划分为多个不重叠的区间（线段），每个节点对应一个区间，通过递归实现操作。
2.1 线段树结构：区间的完全二叉树划分
线段树是一棵完全二叉树，满足：
根节点对应整个数组区间
[1, n]；每个非叶子节点将区间分为左子区间
[l, mid]和右子区间[mid+1, r]（mid = (l+r)/2）；叶子节点对应单个元素（
l = r），存储原始数组的值；非叶子节点存储对应区间的聚合信息（如和、最大值），由子节点信息合并得到。
数组 [1,3,5,7,9,11] 的线段树结构
空间需求：为什么开 4 倍大小？
线段树的节点数最多为 4n（当 n 不是 2 的幂时，需补全为完全二叉树以保证递归逻辑统一），因此代码中通常定义 tree[maxn << 2]（maxn << 2即 maxn * 4），避免数组越界。
2.2 单点更新的线段树（基础版）
单点更新的线段树支持 “单点修改” 和 “区间查询（求和 / 最大值）”，核心操作包括建树、单点修改、区间查询，均通过递归实现。
2.2.1 建树（build）：初始化线段树
逻辑：递归划分区间，叶子节点赋值为原始数组元素，非叶子节点通过子节点信息合并（如 sum = 左 sum + 右 sum，max=max (左 max, 右 max)），完成从叶子到根的信息聚合。
代码实现：
struct Node {
int left, right; // 区间左右端点
int max, sum; // 区间最大值和区间和
};
const int maxn = 100010;
Node tree\[maxn << 2]; // 开4倍空间
int a\[maxn]; // 原始数组
int n;
void build(int m, int l, int r) { // m：节点编号，l/r：区间左右端点
tree\[m].left = l;
tree\[m].right = r;
if (l == r) { // 叶子节点：对应单个元素，直接赋值
tree\[m].max = a\[l];
tree\[m].sum = a\[l];
return;
}
int mid = (l + r) >> 1; // 划分左右子区间（等价于(l+r)/2，效率更高）
build(m << 1, l, mid); // 左子节点：编号m\*2，区间\[l, mid]
build(m << 1 | 1, mid + 1, r); // 右子节点：编号m\*2+1，区间\[mid+1, r]
// 合并子节点信息，更新当前节点的聚合值
tree\[m].max = max(tree\[m << 1].max, tree\[m << 1 | 1].max);
tree\[m].sum = tree\[m << 1].sum + tree\[m << 1 | 1].sum;
}
2.2.2 单点修改（update）：更新某个位置的值
逻辑：递归找到目标叶子节点（对应待修改位置），更新其值，再回溯合并所有父节点的聚合信息 —— 因为父节点的信息依赖子节点，子节点变化后需同步更新。
代码实现：
// 单点更新：将位置pos的值增加val
void update(int m, int pos, int val) {
// 找到目标叶子节点（区间左右端点均为pos）
if (tree\[m].left == pos && tree\[m].right == pos) {
tree\[m].max += val;
tree\[m].sum += val;
return;
}
int mid = (tree\[m].left + tree\[m].right) >> 1;
// 根据pos所在区间，递归更新左/右子树
if (pos <= mid) update(m << 1, pos, val);
else update(m << 1 | 1, pos, val);
// 回溯合并子节点信息，更新当前节点的聚合值
tree\[m].max = max(tree\[m << 1].max, tree\[m << 1 | 1].max);
tree\[m].sum = tree\[m << 1].sum + tree\[m << 1 | 1].sum;
}
2.2.3 区间查询（querySum/queryMax）：求区间和 / 最大值
逻辑：递归判断当前节点区间与目标区间的关系，分三种情况处理：
完全覆盖：当前节点区间恰好是目标区间的子集，直接返回当前节点的聚合值（sum/max）；
部分重叠：当前节点区间与目标区间有交集但不完全覆盖，递归查询左 / 右子树，合并结果；
无重叠：当前节点区间与目标区间无交集，返回无效值（如 sum 返回 0，max 返回 -∞）。
区间和查询代码：
// 查询区间\[l, r]的和
int querySum(int m, int l, int r) {
// 完全覆盖：直接返回当前节点sum
if (l == tree\[m].left && r == tree\[m].right) {
return tree\[m].sum;
}
int mid = (tree\[m].left + tree\[m].right) >> 1;
if (r <= mid) { // 目标区间在左子树
return querySum(m << 1, l, r);
} else if (l > mid) { // 目标区间在右子树
return querySum(m << 1 | 1, l, r);
} else { // 跨左右子树：合并左右子树的查询结果
return querySum(m << 1, l, mid) + querySum(m << 1 | 1, mid + 1, r);
}
}
2.3 区间更新的线段树：懒标记（Lazy Tag）优化
如果直接对区间更新（如给 [L,R] 加 val），递归到每个叶子节点的时间复杂度为 O (n)，效率低下。懒标记的核心思想是 “延迟更新”：
给需要更新的区间节点打一个 “标记”，暂时不更新其子节点 —— 避免不必要的递归；
当后续操作（查询 / 修改）需要访问该节点的子节点时，再将标记 “下推”（pushdown）到子节点，完成实际更新，确保数据正确性。
2.3.1 懒标记核心操作
懒标记的线段树需新增两个关键操作：pushdown（下推标记）和 maintain（合并子节点信息），同时节点结构需新增 “懒标记” 字段（如 addv表示区间增量）。
1. 节点结构定义
typedef long long ll;
const int maxn = 100010;
struct Node {
ll l, r; // 区间左右端点
ll addv, sum; // 懒标记（区间增量）和区间和
} tree\[maxn << 2];
2. 维护子节点信息（maintain）
逻辑：非叶子节点的聚合信息（如 sum）由左右子节点的信息合并得到，在子节点更新后调用，确保当前节点信息正确。
// 维护当前节点的sum：由左右子节点sum合并
void maintain(int id) {
if (tree\[id].l >= tree\[id].r) {
return; // 叶子节点无子女，无需维护
}
tree\[id].sum = tree\[id<<1].sum + tree\[id<<1|1].sum;
}
3. 下推懒标记（pushdown）
逻辑：将当前节点的懒标记传递给左右子节点，更新子节点的 sum 和标记，然后清除当前节点的标记 —— 确保子节点后续操作时数据正确。
void pushdown(int id) {
if (tree\[id].l >= tree\[id].r) return; // 叶子节点无子女，无需下推
if (tree\[id].addv) { // 存在未下推的标记
ll tmp = tree\[id].addv;
// 更新左子节点：sum += 标记值 \* 区间长度（每个元素加tmp），标记累加
tree\[id<<1].addv += tmp;
tree\[id<<1].sum += (tree\[id<<1].r - tree\[id<<1].l + 1) \* tmp;
// 更新右子节点：逻辑与左子节点一致
tree\[id<<1|1].addv += tmp;
tree\[id<<1|1].sum += (tree\[id<<1|1].r - tree\[id<<1|1].l + 1) \* tmp;
// 清除当前节点标记：标记已下推，当前节点无未处理的增量
tree\[id].addv = 0;
}
}
懒标记下推流程
假设父节点 [1-4]有标记 addv=2（表示该区间所有元素需加 2），下推过程如下：
4. 区间更新（updateAdd）
逻辑：递归找到与目标区间重叠的节点，根据重叠情况处理：
完全覆盖：打标记并更新当前节点 sum，不递归子节点（延迟更新）；
部分重叠：先下推标记（确保子节点数据正确），再递归更新左 / 右子树，最后调用
maintain合并子节点信息。
代码实现：
// 区间更新：给区间\[l, r]的所有元素加val
void updateAdd(int id, ll l, ll r, ll val) {
// 完全覆盖：打标记并更新sum，延迟更新子节点
if (tree\[id].l >= l && tree\[id].r <= r) {
tree\[id].addv += val;
tree\[id].sum += (tree\[id].r - tree\[id].l + 1) \* val;
return;
}
pushdown(id); // 部分重叠：先下推标记，确保子节点数据正确
ll mid = (tree\[id].l + tree\[id].r) >> 1;
if (l <= mid) updateAdd(id<<1, l, r, val); // 递归更新左子树
if (mid < r) updateAdd(id<<1|1, l, r, val); // 递归更新右子树
maintain(id); // 合并子节点信息，更新当前节点sum
}
2.4 线段树优缺点
三、树状数组 vs 线段树：如何选择？
四、总结
树状数组是 “轻量级选手”：适合简单的区间和问题，实现快、运行快，优先用于单点修改 + 区间和查询场景，是此类问题的 “最优解”。
线段树是 “全能选手”：适合复杂的区间操作（如区间最大值、区间修改），功能强大但实现较繁琐，是区间问题的 “通用解”。
选择的核心原则：能用量少的工具解决问题，就不使用复杂工具。例如，求 “区间和 + 单点修改” 用树状数组，求 “区间最大值 + 区间修改” 用线段树 —— 在保证正确性的前提下，兼顾代码效率和开发效率。
