线段树
线段树（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
