数据结构之线段树
线段树
线段树（Segment Tree）是一种高效的数据结构，广泛应用于计算机科学和算法中，特别是在处理区间查询和更新问题时表现出色。以下是对线段树的详细解释：
一、基本概念
线段树是一种二叉搜索树，是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树可以在 
的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
原理其实是分治思想。它将整个区间划分成一些单元区间，具有对数级别的高度，从而保证了高效的查询和更新操作。
二、基本结构
- 根结点：代表整个区间。
- 内部结点：每个内部结点都代表一个区间，并将其划分为左右两个子区间，分别由左孩子和右孩子表示。
- 叶结点：代表单元区间，每个叶结点对应原始数据中的一个元素。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。
三、示例应用
假设有一个长度为N的数组a，需要频繁地查询任意区间[l,r]的最小值和以及更新数组中的某个元素。使用线段树可以高效地解决这些问题。以下是一个简单的线段树实现示例（以Python代码表示）：
class SegmentTree: def __init__(self, nums): self.nums = nums self.n = len(nums) # 初始化线段树，大小为4倍的原数组长度，因为线段树是完全二叉树 self.tree = [float('inf')] * (4 * self.n) self.build_tree(0, 0, self.n - 1) def build_tree(self, tree_index, l, r): # 如果到达了叶节点 if l == r: self.tree[tree_index] = self.nums[l] return # 计算左右子节点的索引 left_child = 2 * tree_index + 1 right_child = 2 * tree_index + 2 # 递归构建左右子树 mid = (l + r) // 2 self.build_tree(left_child, l, mid) self.build_tree(right_child, mid + 1, r) # 当前节点的值是其左右子节点值的最小值 self.tree[tree_index] = min(self.tree[left_child], self.tree[right_child]) def query(self, l, r): return self.query_tree(0, 0, self.n - 1, l, r) def query_tree(self, tree_index, seg_l, seg_r, query_l, query_r): # 如果查询区间完全包含了当前线段树节点代表的区间 if query_l <= seg_l and seg_r <= query_r: return self.tree[tree_index] # 如果查询区间与当前线段树节点代表的区间没有交集 if query_l > seg_r or query_r < seg_l: return float('inf') # 计算左右子节点的索引 left_child = 2 * tree_index + 1 right_child = 2 * tree_index + 2 # 递归查询左右子树，并取最小值 mid = (seg_l + seg_r) // 2 left_min = self.query_tree(left_child, seg_l, mid, query_l, query_r) right_min = self.query_tree(right_child, mid + 1, seg_r, query_l, query_r) return min(left_min, right_min) def update(self, index, value): self.update_tree(0, 0, self.n - 1, index, value) def update_tree(self, tree_index, seg_l, seg_r, index, value): # 如果到达了叶节点 if seg_l == seg_r: self.nums[index] = value self.tree[tree_index] = value return # 计算左右子节点的索引 left_child = 2 * tree_index + 1 right_child = 2 * tree_index + 2 # 递归更新左右子树 mid = (seg_l + seg_r) // 2 if index <= mid: self.update_tree(left_child, seg_l, mid, index, value) else: self.update_tree(right_child, mid + 1, seg_r, index, value) # 当前节点的值是其左右子节点值的最小值 self.tree[tree_index] = min(self.tree[left_child], self.tree[right_child]) # 示例用法
nums = [1, 3, 2, 7, 9, 11]
seg_tree = SegmentTree(nums) # 查询区间[1, 3]的最小值
print(seg_tree.query(1, 3)) # 输出: 2 # 更新索引2处的值为0
seg_tree.update(2, 0) # 再次查询区间[1, 3]的最小值
print(seg_tree.query(1, 3)) # 输出: 0