企业官网建设流程全解析

线段树是一种用于高效处理区间查询（如区间求和、最值）和区间更新操作的二叉树数据结构，它将一个区间递归地划分为若干子区间进行管理，使得单次操作的时间复杂度通常为 O(log n)。

核心原理与结构

线段树基于分治思想，将区间[1, n]表示为一棵二叉树：

• 根节点：存储整个区间[1, n]的统计信息（如区间和）。
• 内部节点：每个节点代表一个区间[l, r]。若l != r，则其左右子节点分别代表[l, mid]和[mid+1, r]，其中mid = (l + r) / 2。
• 叶子节点：代表长度为1的区间[i, i]，直接存储原数组第i个元素的值。

基本操作与代码实现（以区间求和为例）

以下为 C++ 实现，包含建树、区间查询、单点更新及使用懒惰标记的区间更新。

#include <vector> #include <iostream> using namespace std; class SegmentTree { private: vector<int> tree; // 线段树数组 vector<int> lazy; // 懒惰标记数组 int n; // 原始数组大小 // 建树 void build(int node, int l, int r, const vector<int>& 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 vector<int>& 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() { vector<int> arr = {0, 1, 3, 5, 7, 9, 11}; // arr[0]占位，有效数据从下标1开始 SegmentTree st(arr); cout << "区间[2,5]的和: " << st.queryRange(2, 5) << endl; // 输出: 24 (3+5+7+9) st.updateSingle(3, 10); // 将下标3的元素改为10 cout << "更新后区间[2,5]的和: " << st.queryRange(2, 5) << endl; // 输出: 29 (3+10+7+9) st.updateRange(2, 4, 2); // 区间[2,4]每个元素加2 cout << "区间更新后[2,5]的和: " << st.queryRange(2, 5) << endl; // 输出: 35 (5+12+9+9) return 0; }

关键特性与对比

常见变体与应用场景

1. 区间最值线段树：将合并操作从求和改为求最大值或最小值，常用于 RMQ（Range Minimum Query）问题 。
2. 染色问题线段树：每个节点可记录区间颜色状态，用于处理区间覆盖与颜色种类查询 。
3. 可持久化线段树（主席树）：通过复用历史版本的节点，支持查询任意历史版本的信息，常用于区间第 K 大问题 。
4. 动态开点线段树：在节点被访问时才创建，适用于值域极大（如[1, 1e9]）但实际使用点稀疏的场景。
5. 权值线段树：将值域作为区间，统计值的出现次数，可用于解决逆序对、排名等问题。

核心优化：懒惰标记 (Lazy Tag)

懒惰标记是线段树支持高效区间更新的关键。其核心思想是：当更新完全覆盖某个节点区间时，仅更新该节点的值并打上标记，表示其子节点有待更新，而非立即递归更新所有子节点。只有当后续查询或更新需要访问子节点时，才将标记下推（pushDown）。这避免了不必要的递归，将区间更新的复杂度从 O(n) 降为 O(log n)。

参考来源

• HDU5023：线段树应用于染色问题
• 【数据结构】可持久化线段树：图解原理逻辑及版本实现细节（洛谷 P3919 C++代码）
• 数据结构学习——线段树的C语言实现
• 线段树详解（含代码实现经过测试）
• 线段树（segment tree)，看这一篇就够了