线段树是一种用于高效处理区间查询如区间求和、最值和区间更新操作的二叉树数据结构它将一个区间递归地划分为若干子区间进行管理使得单次操作的时间复杂度通常为 O(log n)。核心原理与结构线段树基于分治思想将区间[1, n]表示为一棵二叉树根节点存储整个区间[1, n]的统计信息如区间和。内部节点每个节点代表一个区间[l, r]。若l ! r则其左右子节点分别代表[l, mid]和[mid1, r]其中mid (l r) / 2。叶子节点代表长度为1的区间[i, i]直接存储原数组第i个元素的值。基本操作与代码实现以区间求和为例以下为 C 实现包含建树、区间查询、单点更新及使用懒惰标记的区间更新。#include vector #include iostream using namespace std; class SegmentTree { private: vectorint tree; // 线段树数组 vectorint lazy; // 懒惰标记数组 int n; // 原始数组大小 // 建树 void build(int node, int l, int r, const vectorint arr) { if (l r) { tree[node] arr[l]; return; } int mid (l r) / 2; build(node * 2, l, mid, arr); build(node * 2 1, mid 1, r, arr); tree[node] tree[node * 2] tree[node * 2 1]; // 合并左右子树信息 } // 下推懒惰标记 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 * 2 1] lazy[node] * (r - mid); lazy[node * 2 1] 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]; // 当前区间完全在查询范围内 pushDown(node, l, r); // 查询前下推标记 int mid (l r) / 2; int sum 0; if (ql mid) sum query(node * 2, l, mid, ql, qr); if (qr mid) sum query(node * 2 1, mid 1, r, ql, qr); return sum; } // 单点更新 void updatePoint(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) updatePoint(node * 2, l, mid, idx, val); else updatePoint(node * 2 1, mid 1, r, idx, val); tree[node] tree[node * 2] tree[node * 2 1]; // 更新父节点 } // 区间更新使用懒惰标记 void updateRange(int node, int l, int r, int ul, int ur, int val) { if (ul l r ur) { tree[node] val * (r - l 1); // 更新当前节点值 lazy[node] val; // 打上懒惰标记 return; } pushDown(node, l, r); // 下推现有标记 int mid (l r) / 2; if (ul mid) updateRange(node * 2, l, mid, ul, ur, val); if (ur mid) updateRange(node * 2 1, mid 1, r, ul, ur, val); tree[node] tree[node * 2] tree[node * 2 1]; // 合并子节点信息 } public: SegmentTree(const vectorint arr) { n arr.size()1; // 假设arr下标从1开始 tree.resize(4 * n); lazy.resize(4 * n, 0); build(1, 1, n, arr); } int queryRange(int l, int r) { return query(1, 1, n, l, r); } void updateSingle(int idx, int val) { updatePoint(1, 1, n, idx, val); } void updateRange(int l, int r, int val) { updateRange(1, 1, n, l, r, val); } }; // 使用示例 int main() { vectorint arr {0, 1, 3, 5, 7, 9, 11}; // arr[0]占位有效数据从下标1开始 SegmentTree st(arr); cout 区间[2,5]的和: st.queryRange(2, 5) endl; // 输出: 24 (3579) st.updateSingle(3, 10); // 将下标3的元素改为10 cout 更新后区间[2,5]的和: st.queryRange(2, 5) endl; // 输出: 29 (31079) st.updateRange(2, 4, 2); // 区间[2,4]每个元素加2 cout 区间更新后[2,5]的和: st.queryRange(2, 5) endl; // 输出: 35 (51299) return 0; }关键特性与对比特性描述时间复杂度区间查询查询任意区间[l, r]的聚合信息和、最值等O(log n)单点更新修改原数组中单个元素的值O(log n)区间更新配合懒惰标记 (Lazy Propagation)可高效地对整个区间进行统一修改如区间加一个值O(log n)空间复杂度通常需要 4*n 的数组存储树节点最坏情况O(n)适用场景频繁的区间查询、区间更新操作原数组规模大需要优于 O(n) 的复杂度-常见变体与应用场景区间最值线段树将合并操作从求和改为求最大值或最小值常用于 RMQRange Minimum Query问题 。染色问题线段树每个节点可记录区间颜色状态用于处理区间覆盖与颜色种类查询 。可持久化线段树主席树通过复用历史版本的节点支持查询任意历史版本的信息常用于区间第 K 大问题 。动态开点线段树在节点被访问时才创建适用于值域极大如[1, 1e9]但实际使用点稀疏的场景。权值线段树将值域作为区间统计值的出现次数可用于解决逆序对、排名等问题。核心优化懒惰标记 (Lazy Tag)懒惰标记是线段树支持高效区间更新的关键。其核心思想是当更新完全覆盖某个节点区间时仅更新该节点的值并打上标记表示其子节点有待更新而非立即递归更新所有子节点。只有当后续查询或更新需要访问子节点时才将标记下推pushDown。这避免了不必要的递归将区间更新的复杂度从 O(n) 降为 O(log n)。参考来源HDU5023线段树应用于染色问题【数据结构】可持久化线段树图解原理逻辑及版本实现细节洛谷 P3919 C代码数据结构学习——线段树的C语言实现线段树详解含代码实现经过测试线段树segment tree)看这一篇就够了
