划分树（Segment Tree）详解：原理、实现与应用

1. 什么是划分树划分树Segment Tree又称线段树是一种用于高效处理区间查询和区间更新的二叉树数据结构。它将一个线性区间通常是数组递归地划分成若干个子区间并将每个子区间的聚合信息如区间和、最大值、最小值等存储在对应的树节点中。划分树的核心思想是分治与预处理通过一次 O(n log n) 的建树操作将原始数据组织成树形结构从而将后续的区间查询和更新操作的时间复杂度降至 O(log n)。2. 划分树的结构与性质2.1 基本结构划分树是一棵完全二叉树通常用数组存储其每个节点代表原始数组的一个连续区间 [l, r]根节点代表整个数组区间 [0, n-1]。内部节点代表其父节点区间的左半部分或右半部分。叶子节点代表长度为 1 的区间即原始数组的单个元素。对于区间 [l, r]其中点 mid (l r) / 2其左右子节点分别代表左子节点区间 [l, mid]右子节点区间 [mid1, r]2.2 存储的信息每个树节点通常存储以下信息区间范围l, r区间的左右端点。聚合值根据具体问题而定例如区间和sum区间最大值max区间最小值min区间乘积product区间 GCD/LCM 等懒标记Lazy Tag用于支持区间更新实现延迟传播。3. 划分树的基本操作3.1 建树Build采用递归方式自底向上构建划分树// 以区间和为例 void build(int node, int l, int r) { if (l r) { tree[node] arr[l]; // 叶子节点 return; } int mid (l r) / 2; build(node*2, l, mid); // 构建左子树 build(node*21, mid1, r); // 构建右子树 tree[node] tree[node*2] tree[node*21]; // 合并左右子树信息 }时间复杂度O(n)因为每个节点恰好被访问一次。3.2 区间查询Query查询区间 [ql, qr] 的聚合值如区间和int query(int node, int l, int r, int ql, int qr) { // 当前节点区间完全在查询区间内 if (ql l r qr) { return tree[node]; } // 当前节点区间与查询区间无交集 if (r ql || l qr) { return 0; // 对于区间和无交集返回 0 } // 当前节点区间与查询区间部分重叠递归查询左右子树 int mid (l r) / 2; int leftSum query(node*2, l, mid, ql, qr); int rightSum query(node*21, mid1, r, ql, qr); return leftSum rightSum; }时间复杂度O(log n)因为每次递归最多访问树的两条路径。3.3 单点更新Point Update更新数组某个位置的值并更新所有包含该位置的节点void update(int node, int l, int r, int idx, int val) { if (l r) { tree[node] val; // 找到叶子节点 return; } int mid (l r) / 2; if (idx mid) { update(node*2, l, mid, idx, val); } else { update(node*21, mid1, r, idx, val); } tree[node] tree[node*2] tree[node*21]; // 更新父节点 }时间复杂度O(log n)。4. 懒标记Lazy Propagation对于区间更新操作如将区间内所有元素加上一个值如果对每个元素都进行单点更新时间复杂度会退化为 O(n log n)。懒标记技术可以将区间更新的复杂度也优化到 O(log n)。4.1 懒标记原理懒标记的核心思想是延迟更新当更新操作覆盖整个节点区间时不立即更新其所有子节点而是将更新信息记录在该节点的懒标记中。只有当后续查询或更新需要访问子节点时才将懒标记向下传递push down。4.2 带懒标记的区间更新// 懒标记数组 int lazy[MAX_N * 4]; // 下传懒标记 void pushDown(int node, int l, int r) { if (lazy[node] ! 0) { int mid (l r) / 2; // 更新左子节点 tree[node*2] lazy[node] * (mid - l 1); lazy[node*2] lazy[node]; // 更新右子节点 tree[node*21] lazy[node] * (r - mid); lazy[node*21] lazy[node]; // 清空当前节点的懒标记 lazy[node] 0; } } // 区间增加操作 void rangeUpdate(int node, int l, int r, int ql, int qr, int val) { if (ql l r qr) { // 完全覆盖更新当前节点并设置懒标记 tree[node] val * (r - l 1); lazy[node] val; return; } pushDown(node, l, r); // 下传懒标记 int mid (l r) / 2; if (ql mid) { rangeUpdate(node*2, l, mid, ql, qr, val); } if (qr mid) { rangeUpdate(node*21, mid1, r, ql, qr, val); } tree[node] tree[node*2] tree[node*21]; }5. 划分树的应用场景区间求和/最值查询静态或动态数组的区间查询。区间更新给区间内所有元素加上一个值。区间赋值将区间内所有元素设置为同一个值。区间统计查询区间内满足某种条件的元素个数。二维划分树扩展至二维平面用于处理矩阵区间查询。持久化划分树可持久化线段树支持查询历史版本。6. 划分树的优缺点优点高效区间查询和更新均为 O(log n)。灵活支持多种聚合操作和、最值、GCD 等。可扩展通过懒标记支持区间更新可扩展到二维。缺点空间开销需要 O(4n) 的存储空间。实现复杂度懒标记等高级功能代码实现较为复杂。常数较大递归操作带来一定的常数时间开销。7. 代码示例完整的区间和划分树#include iostream #include vector using namespace std; class SegmentTree { private: vectorint tree; vectorint lazy; int n; void build(int node, int l, int r, vectorint arr) { if (l r) { tree[node] arr[l]; return; } int mid (l r) / 2; build(node*2, l, mid, arr); build(node*21, mid1, r, arr); tree[node] tree[node*2] tree[node*21]; } void pushDown(int node, int l, int r) { if (lazy[node] ! 0) { int mid (l r) / 2; tree[node*2] lazy[node] * (mid - l 1); lazy[node*2] lazy[node]; tree[node*21] lazy[node] * (r - mid); lazy[node*21] lazy[node]; lazy[node] 0; } } int query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; if (r ql || l qr) return 0; pushDown(node, l, r); int mid (l r) / 2; return query(node*2, l, mid, ql, qr) query(node*21, mid1, r, ql, qr); } void rangeUpdate(int node, int l, int r, int ql, int qr, int val) { if (ql l r qr) { tree[node] val * (r - l 1); lazy[node] val; return; } pushDown(node, l, r); int mid (l r) / 2; if (ql mid) rangeUpdate(node*2, l, mid, ql, qr, val); if (qr mid) rangeUpdate(node*21, mid1, r, ql, qr, val); tree[node] tree[node*2] tree[node*21]; } public: SegmentTree(vectorint arr) { n arr.size(); tree.resize(4 * n); lazy.resize(4 * n, 0); build(1, 0, n-1, arr); } int query(int l, int r) { return query(1, 0, n-1, l, r); } void rangeUpdate(int l, int r, int val) { rangeUpdate(1, 0, n-1, l, r, val); } }; int main() { vectorint arr {1, 3, 5, 7, 9, 11}; SegmentTree st(arr); cout 区间 [1, 3] 的和: st.query(1, 3) endl; // 35715 st.rangeUpdate(1, 4, 2); // 给索引 1~4 的元素都加 2 cout 更新后区间 [1, 3] 的和: st.query(1, 3) endl; // 57921 return 0; }8. 总结划分树是解决区间查询与更新问题的利器尤其适合需要频繁进行区间操作的场景。掌握划分树的基本原理、建树、查询、更新以及懒标记技术能够帮助你在算法竞赛和工程开发中高效处理各类区间问题。在实际应用中需要根据具体问题选择合适的聚合函数并注意空间复杂度和常数优化。对于更复杂的需求还可以探索划分树的变种如权值线段树、可持久化线段树和动态开点线段树等。