数据结构之线段树

线段树

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