线段树（Segment Tree）详解：从原理到实现

1. 什么是线段树线段树Segment Tree是一种用于处理区间查询和区间更新的高效数据结构。它将一个区间划分成若干个子区间每个节点存储对应区间的信息如区间和、最大值、最小值等从而支持在 O(log n) 时间内完成区间查询和单点/区间更新操作。2. 线段树的核心思想线段树的核心思想是分治和递归将整个区间 [1, n] 作为根节点递归地将每个区间一分为二左子节点存储左半区间右子节点存储右半区间直到区间长度为 1叶子节点每个节点存储其对应区间的聚合信息3. 线段树的基本操作3.1 建树Build从数组构建线段树时间复杂度 O(n)。class SegmentTree { private int[] tree; private int n; public SegmentTree(int[] nums) { n nums.length; tree new int[4 * n]; // 通常开4倍空间 build(nums, 1, 0, n - 1); } private void build(int[] nums, int node, int start, int end) { if (start end) { tree[node] nums[start]; } else { int mid (start end) / 2; build(nums, node * 2, start, mid); build(nums, node * 2 1, mid 1, end); tree[node] tree[node * 2] tree[node * 2 1]; // 区间和 } } }3.2 区间查询Query查询区间 [l, r] 的聚合值时间复杂度 O(log n)。public int query(int l, int r) { return query(1, 0, n - 1, l, r); } private int query(int node, int start, int end, int l, int r) { if (r start || end l) { return 0; // 区间无交集 } if (l start end r) { return tree[node]; // 当前区间完全包含在查询区间内 } int mid (start end) / 2; int leftSum query(node * 2, start, mid, l, r); int rightSum query(node * 2 1, mid 1, end, l, r); return leftSum rightSum; }3.3 单点更新Update更新单个元素的值时间复杂度 O(log n)。public void update(int index, int val) { update(1, 0, n - 1, index, val); } private void update(int node, int start, int end, int index, int val) { if (start end) { tree[node] val; } else { int mid (start end) / 2; if (index mid) { update(node * 2, start, mid, index, val); } else { update(node * 2 1, mid 1, end, index, val); } tree[node] tree[node * 2] tree[node * 2 1]; } }4. 线段树的变种与应用4.1 支持区间更新的线段树带懒标记通过懒标记Lazy Propagation技术可以在 O(log n) 时间内完成区间更新。class LazySegmentTree { private int[] tree; private int[] lazy; private int n; // 区间更新将 [l, r] 内的每个元素增加 val private void updateRange(int node, int start, int end, int l, int r, int val) { if (lazy[node] ! 0) { tree[node] (end - start 1) * lazy[node]; if (start ! end) { lazy[node * 2] lazy[node]; lazy[node * 2 1] lazy[node]; } lazy[node] 0; } if (start end || start r || end l) { return; } if (start l end r) { tree[node] (end - start 1) * val; if (start ! end) { lazy[node * 2] val; lazy[node * 2 1] val; } return; } int mid (start end) / 2; updateRange(node * 2, start, mid, l, r, val); updateRange(node * 2 1, mid 1, end, l, r, val); tree[node] tree[node * 2] tree[node * 2 1]; } }4.2 常见应用场景区间和查询求任意区间内元素的和区间最值查询求区间最大值或最小值区间修改批量增加、减少或赋值逆序对统计结合离散化使用区间覆盖问题如颜色覆盖、线段覆盖等5. 线段树的优缺点优点查询和更新效率高O(log n)支持多种区间操作和、最值、乘积等结构清晰易于理解和实现缺点空间复杂度较高需要 4n 的数组空间实现相对复杂特别是带懒标记的版本对于某些特殊问题可能有更优的数据结构如树状数组6. 线段树 vs 树状数组特性线段树树状数组空间复杂度O(4n)O(n)代码复杂度较高较低功能支持全面区间查询、区间更新有限主要前缀和学习曲线较陡平缓7. 实战例题例题区间和查询LeetCode 307设计一个数据结构支持以下两种操作update(index, val)将下标为 index 的元素更新为 valsumRange(left, right)返回区间 [left, right] 内元素的和// 线段树解法 class NumArray { private SegmentTree segTree; public NumArray(int[] nums) { segTree new SegmentTree(nums); } public void update(int index, int val) { segTree.update(index, val); } public int sumRange(int left, int right) { return segTree.query(left, right); } }8. 总结线段树是解决区间问题的利器虽然实现相对复杂但一旦掌握能高效解决许多经典问题。学习建议先理解基本线段树区间和的实现掌握懒标记技术实现区间更新练习变种问题最值、乘积、覆盖等对比学习树状数组根据问题特点选择合适的数据结构