线段树是一种用于高效处理区间查询和区间更新的数据结构。它通常用于解决诸如区间求和、区间最小值/最大值查询等问题。
加载中…
应用场景：区间求和/最值 · 区间修改 · 动态统计
线段树是一种用于高效处理区间查询和区间更新的数据结构。它通常用于解决诸如区间求和、区间最小值/最大值查询等问题。
交互式动画演示，可调整参数并单步执行。
全屏打开graph TD R[1..n] --> L[1..n/2] R --> Rt[n/2+1..n] L --> LL[1..n/4] L --> LR[n/4+1..n/2] Rt --> RL[n/2+1..3n/4] Rt --> RR[3n/4+1..n] LL --> A1[叶子: 单元素] LR --> A2[叶子: 单元素]
如果区间有 n 个元素，数组表示需要 4n 个节点
结构图解（数组 [2, 5, 1, 4, 9, 3] 的求和线段树）：
[0,5] sum=24
/ \
[0,2] sum=8 [3,5] sum=16
/ \ / \
[0,1] sum=7 [2,2]=1 [3,4] sum=13 [5,5]=3
/ \ / \
[0,0]=2 [1,1]=5 [3,3]=4 [4,4]=9
规律：
- 节点 [l,r] 的左孩子 = [l, mid]，右孩子 = [mid+1, r]
- 树高 = ⌈log₂n⌉ + 1
- 每层最多覆盖整个区间 → 查询只需访问 O(log n) 个节点
查询过程模拟（查询 [1, 4] 的和）：
query([1,4]) 从根 [0,5] 开始：
[0,5] 不被 [1,4] 完全覆盖 → 分裂为 [0,2] 和 [3,5]
├── [0,2] 不被完全覆盖 → 分裂为 [0,1] 和 [2,2]
│ ├── [0,1] 不被完全覆盖 → 分裂为 [0,0] 和 [1,1]
│ │ ├── [0,0] 与查询无交集 → 返回 0（剪枝！）
│ │ └── [1,1] 被完全覆盖 → 返回 5 ✓
│ └── [2,2] 被完全覆盖 → 返回 1 ✓
└── [3,5] 不被完全覆盖 → 分裂为 [3,4] 和 [5,5]
├── [3,4] 被完全覆盖 → 返回 13 ✓（不再往下走！）
└── [5,5] 与查询无交集 → 返回 0（剪枝！）
结果 = 5 + 1 + 13 = 19
实际只访问了 9 个节点（而非全部 11 个）
核心洞察：任何区间 [l, r] 最多被分解为 O(log n) 个"恰好覆盖"的节点，这就是线段树高效的本质。
区间更新如果逐个修改叶子节点，复杂度退化为 O(n)。懒标记的思想：更新时如果当前节点被完全覆盖，只在该节点打上标记，延迟向子节点传播，等到真正需要访问子节点时才下推。
update([3,4], +2) 的过程：
更新前: [0,5]=24
/ \
[0,2]=8 [3,5]=16
/ \
[3,4]=13 [5,5]=3
更新时: [3,4] 被完全覆盖 → 直接修改：
tree[3,4] += 2×2 = 17, lazy[3,4] += 2
回溯更新父节点: [3,5]=20, [0,5]=28
此时 [3,3] 和 [4,4] 的值还是旧的！
但没关系——等下次查询访问到它们时再下推
下推（pushDown）: 访问 [3,4] 的子节点前：
lazy[3,3] += 2, tree[3,3] += 2
lazy[4,4] += 2, tree[4,4] += 2
lazy[3,4] = 0 （标记清零）
public class SegmentTree {
private int[] tree;
private int[] lazy;
private int n;
public SegmentTree(int[] nums) {
n = nums.length;
tree = new int[4 * n];
lazy = new int[4 * n];
buildTree(nums, 0, 0, n - 1);
}
private void buildTree(int[] nums, int idx, int left, int right) {
if (left == right) {
tree[idx] = nums[left];
return;
}
int mid = left + (right - left) / 2;
buildTree(nums, idx * 2 + 1, left, mid);
buildTree(nums, idx * 2 + 2, mid + 1, right);
tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
}
private void pushDown(int idx, int start, int end) {
if (lazy[idx] != 0) {
int mid = start + (end - start) / 2;
int l = idx * 2 + 1, r = idx * 2 + 2;
tree[l] += lazy[idx] * (mid - start + 1);
tree[r] += lazy[idx] * (end - mid);
lazy[l] += lazy[idx];
lazy[r] += lazy[idx];
lazy[idx] = 0;
}
}
public int query(int left, int right) {
return query(0, 0, n - 1, left, right);
}
private int query(int idx, int start, int end, int left, int right) {
if (start > right || end < left) return 0;
if (left <= start && end <= right) return tree[idx];
pushDown(idx, start, end); // 访问子节点前先下推
int mid = start + (end - start) / 2;
return query(idx * 2 + 1, start, mid, left, right) +
query(idx * 2 + 2, mid + 1, end, left, right);
}
public void update(int left, int right, int val) {
update(0, 0, n - 1, left, right, val);
}
private void update(int idx, int start, int end, int left, int right, int val) {
if (start > right || end < left) return;
if (left <= start && end <= right) {
tree[idx] += val * (end - start + 1);
lazy[idx] += val;
return;
}
pushDown(idx, start, end); // 访问子节点前先下推
int mid = start + (end - start) / 2;
update(idx * 2 + 1, start, mid, left, right, val);
update(idx * 2 + 2, mid + 1, end, left, right, val);
tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
}
}| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 构建 | O(n) | 每个节点只访问一次 |
| 区间查询 | O(log n) | 每层最多访问 4 个节点 |
| 区间更新 | O(log n) | 懒标记保证不深入无关子树 |
| 空间 | O(4n) | 数组开 4n 是安全上界 |
为什么查询是 O(log n)：区间 [l,r] 在每一层最多命中 2 个"边界节点"（左边一个、右边一个），中间的整块节点直接返回。总访问节点数 ≤ 4·log₂n。
| 维度 | 线段树 | 树状数组（BIT） |
|---|---|---|
| 代码量 | 较长（~60行） | 短（~15行） |
| 区间更新+区间查询 | ✅ 懒标记天然支持 | 需要差分技巧 |
| 可维护的信息 | 任意可合并信息（sum/min/max/gcd） | 主要是前缀和类 |
| 常数 | 较大（递归开销） | 小（位运算） |
| 扩展性 | 强（可持久化、扫描线、动态开点） | 弱 |
| 面试建议 | 必须掌握 | 了解即可 |
选择原则：能用前缀和/差分解决的用 BIT，需要区间最值、区间赋值等复杂操作用线段树。
| 题目 | 难度 | 线段树用法 |
|---|---|---|
| 区域和检索-可修改（LC 307） | 🟡 Medium | 单点更新 + 区间求和 |
| 矩形面积 II（LC 850） | 🔴 Hard | 扫描线 + 区间覆盖计数 |
| 天际线问题（LC 218） | 🔴 Hard | 扫描线 or 分治 |
| 我的日程安排表 III（LC 732） | 🔴 Hard | 区间加 + 全局最大值 |
| 区间列表的交集（LC 986） | 🟡 Medium | 双指针即可，无需线段树 |
1. 忘记 pushDown
最常见的 bug：区间更新打了懒标记，但查询时不下推，导致子节点值过期。规则：只要准备递归进入子节点，必须先 pushDown。
2. 数组开太小
// ❌ 2n 不够（线段树不是完全二叉树）
tree = new int[2 * n];
// ✅ 4n 是安全上界
tree = new int[4 * n];
3. pushDown 时忘记乘区间长度
// ❌ tree[l] += lazy[idx]; （左孩子覆盖多个元素！）
// ✅ 必须乘子区间的元素个数
tree[l] += lazy[idx] * (mid - start + 1);
tree[r] += lazy[idx] * (end - mid);
4. 区间边界判断方向写反
// ❌ if (start > left || end < right) （与查询区间比较）
// ✅ 与当前节点区间比较
if (start > right || end < left) return 0; // 无交集
if (left <= start && end <= right) return tree[idx]; // 完全覆盖
练习推荐：完成 区域和检索 相关题目后，尝试用线段树重新求解。