线段树

线段树（Segment Tree）是一种用于高效处理区间查询和区间更新的树形数据结构。它能够在 $O (\log n)$ 时间内完成区间查询（如区间求和、区间最小值等）和单点/区间更新操作，广泛应用于解决各种区间操作问题。

基本概念[编辑 | 编辑源代码]

线段树是一种平衡二叉树，其中每个叶子节点存储原始数据的一个元素，而每个非叶子节点存储其子节点对应区间的某种聚合信息（如区间和、区间最大值等）。线段树的构建、查询和更新操作均基于递归实现。

结构特点[编辑 | 编辑源代码]

叶子节点：存储原始数组的单个元素。
非叶子节点：存储其子节点对应区间的聚合信息。
区间划分：每个非叶子节点 $[l, r]$ 的左子节点为 $[l, mid]$ ，右子节点为 $[mid + 1, r]$ ，其中 $mid = ⌊ \frac{l + r}{2} ⌋$ 。

实现[编辑 | 编辑源代码]

线段树的实现通常包括三个核心操作：构建、查询和更新。

构建线段树[编辑 | 编辑源代码]

给定数组 $arr = [1, 2, 3, 4]$ ，构建一个求和线段树：

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        # 填充叶子节点
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        # 构建非叶子节点
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, l, r):
        res = 0
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                res += self.tree[l]
                l += 1
            if r % 2 == 0:
                res += self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return res

    def update(self, pos, value):
        pos += self.size
        self.tree[pos] = value
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

# 示例使用
arr = [1, 2, 3, 4]
st = SegmentTree(arr)
print(st.query(1, 3))  # 输出: 9 (2 + 3 + 4)
st.update(2, 5)        # 将arr[2]更新为5
print(st.query(1, 3))  # 输出: 11 (2 + 5 + 4)

查询操作[编辑 | 编辑源代码]

查询区间 $[l, r]$ 的聚合值时，递归检查当前节点区间是否完全包含在查询区间内：

若完全包含，直接返回当前节点的值。
若部分重叠，递归查询左右子节点。

更新操作[编辑 | 编辑源代码]

更新位置 $i$ 的值时，从叶子节点向上更新所有受影响的父节点。

应用场景[编辑 | 编辑源代码]

线段树适用于以下问题： 1. 区间求和/最值查询：如统计数组子数组的和或最大值。 2. 区间更新：如将区间内的所有元素增加一个固定值（需结合懒惰传播技术）。 3. 动态数据维护：当数据频繁更新时，线段树比前缀数组更高效。

实际案例[编辑 | 编辑源代码]

问题：给定一个数组，支持以下操作： 1. 查询区间 $[l, r]$ 的和。 2. 将区间 $[l, r]$ 的所有元素增加 $Δ$ 。

解决方案：使用带懒惰传播的线段树。

class LazySegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        # 填充叶子节点
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        # 构建非叶子节点
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def push(self, node, node_l, node_r):
        if self.lazy[node] != 0:
            self.tree[node] += self.lazy[node] * (node_r - node_l + 1)
            if node < self.size:  # 非叶子节点
                self.lazy[2 * node] += self.lazy[node]
                self.lazy[2 * node + 1] += self.lazy[node]
            self.lazy[node] = 0

    def range_update(self, l, r, delta, node=1, node_l=0, node_r=None):
        if node_r is None:
            node_r = self.size - 1
        self.push(node, node_l, node_r)
        if r < node_l or l > node_r:
            return
        if l <= node_l and node_r <= r:
            self.lazy[node] += delta
            self.push(node, node_l, node_r)
            return
        mid = (node_l + node_r) // 2
        self.range_update(l, r, delta, 2 * node, node_l, mid)
        self.range_update(l, r, delta, 2 * node + 1, mid + 1, node_r)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def range_query(self, l, r, node=1, node_l=0, node_r=None):
        if node_r is None:
            node_r = self.size - 1
        self.push(node, node_l, node_r)
        if r < node_l or l > node_r:
            return 0
        if l <= node_l and node_r <= r:
            return self.tree[node]
        mid = (node_l + node_r) // 2
        return self.range_query(l, r, 2 * node, node_l, mid) + \
               self.range_query(l, r, 2 * node + 1, mid + 1, node_r)

# 示例使用
arr = [1, 2, 3, 4]
lst = LazySegmentTree(arr)
print(lst.range_query(1, 3))  # 输出: 9
lst.range_update(1, 3, 2)     # 区间[1,3]每个元素加2
print(lst.range_query(1, 3))  # 输出: 15 (4 + 5 + 6)

复杂度分析[编辑 | 编辑源代码]

构建： $O (n)$ 。
查询/更新： $O (\log n)$ 。
空间： $O (n)$ （实际分配空间通常为 $2^{⌈ \log_{2} n ⌉ + 1}$ ）。

扩展[编辑 | 编辑源代码]

二维线段树：用于处理矩阵区间查询。
持久化线段树：支持历史版本查询。

模板:Stub