当前位置：首页 > news >正文

线段树：高效区间操作的利器

news 2026/5/12 2:32:04

线段树的基本概念

线段树（Segment Tree）是一种二叉树数据结构，用于高效处理区间查询和区间更新问题。其核心思想是将区间递归划分为若干子区间，每个节点存储对应区间的聚合信息（如求和、最大值、最小值等）。线段树常用于解决静态或动态区间查询问题，时间复杂度通常为 $O(\log n)$。

线段树的构建

线段树的构建基于递归分治。给定一个长度为 $n$ 的数组，根节点表示区间 $[0, n-1]$，每个非叶子节点的左右子节点分别表示区间的左半和右半部分。

关键步骤

初始化节点：每个节点存储区间 $[l, r]$ 的聚合值。
递归划分：若当前区间 $[l, r]$ 不为单点（即 $l \neq r$），则递归构建左右子树，分别处理 $[l, mid]$ 和 $[mid+1, r]$，其中 $mid = \lfloor (l+r)/2 \rfloor$。
合并信息：根据左右子树的聚合值计算当前节点的值（如求和时，父节点值为左右子节点值之和）。

示例代码

struct SegmentTreeNode { int l, r; int sum; // 以区间和为例 SegmentTreeNode *left, *right; SegmentTreeNode(int l, int r) : l(l), r(r), sum(0), left(nullptr), right(nullptr) {} }; SegmentTreeNode* build(int l, int r, vector<int>& nums) { SegmentTreeNode* node = new SegmentTreeNode(l, r); if (l == r) { node->sum = nums[l]; return node; } int mid = (l + r) / 2; node->left = build(l, mid, nums); node->right = build(mid + 1, r, nums); node->sum = node->left->sum + node->right->sum; return node; }

区间查询

线段树的查询通过递归实现，根据目标区间与当前节点区间的重叠情况分三种情况处理：

完全覆盖：当前节点区间完全包含于查询区间，直接返回节点值。
部分重叠：递归查询左右子树并合并结果。
无重叠：返回不影响结果的初始值（如求和时为0）。

示例代码

int query(SegmentTreeNode* node, int l, int r) { if (node->r < l || node->l > r) return 0; // 无重叠 if (l <= node->l && node->r <= r) return node->sum; // 完全覆盖 return query(node->left, l, r) + query(node->right, l, r); // 部分重叠 }

单点更新

单点更新需要递归定位到目标叶子节点，更新其值后回溯调整父节点的聚合值。

示例代码

void update(SegmentTreeNode* node, int index, int val) { if (node->l == node->r) { node->sum = val; return; } int mid = (node->l + node->r) / 2; if (index <= mid) update(node->left, index, val); else update(node->right, index, val); node->sum = node->left->sum + node->right->sum; }

区间更新与懒惰标记

区间更新若直接逐个单点更新效率较低，引入懒惰标记（Lazy Propagation）延迟更新操作。

标记下传：当需要访问子节点时，将当前节点的标记和未完成的更新操作下传给子节点。
标记应用：在查询或更新时检查并处理懒惰标记。

示例代码（带懒惰标记）

struct SegmentTreeNode { int l, r; int sum, lazy; // lazy存储未下传的增量 SegmentTreeNode *left, *right; SegmentTreeNode(int l, int r) : l(l), r(r), sum(0), lazy(0), left(nullptr), right(nullptr) {} }; void pushDown(SegmentTreeNode* node) { if (node->lazy != 0) { node->left->sum += node->lazy * (node->left->r - node->left->l + 1); node->right->sum += node->lazy * (node->right->r - node->right->l + 1); node->left->lazy += node->lazy; node->right->lazy += node->lazy; node->lazy = 0; } } void rangeUpdate(SegmentTreeNode* node, int l, int r, int val) { if (node->r < l || node->l > r) return; if (l <= node->l && node->r <= r) { node->sum += val * (node->r - node->l + 1); node->lazy += val; return; } pushDown(node); rangeUpdate(node->left, l, r, val); rangeUpdate(node->right, l, r, val); node->sum = node->left->sum + node->right->sum; }