编辑“︁线段树”︁

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

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

=== 结构特点 ===
* 叶子节点：存储原始数组的单个元素。
* 非叶子节点：存储其子节点对应区间的聚合信息。
* 区间划分：每个非叶子节点<math>[l, r]</math>的左子节点为<math>[l, \text{mid}]</math>，右子节点为<math>[\text{mid}+1, r]</math>，其中<math>\text{mid} = \lfloor \frac{l + r}{2} \rfloor</math>。

<mermaid>
graph TD
    A["[1, 4] (Sum: 10)"] --> B["[1, 2] (Sum: 3)"]
    A --> C["[3, 4] (Sum: 7)"]
    B --> D["[1, 1] (Sum: 1)"]
    B --> E["[2, 2] (Sum: 2)"]
    C --> F["[3, 3] (Sum: 3)"]
    C --> G["[4, 4] (Sum: 4)"]
</mermaid>

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

=== 构建线段树 ===
给定数组<math>\text{arr} = [1, 2, 3, 4]</math>，构建一个求和线段树：

<syntaxhighlight lang="python">
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)
</syntaxhighlight>

=== 查询操作 ===
查询区间<math>[l, r]</math>的聚合值时，递归检查当前节点区间是否完全包含在查询区间内：
* 若完全包含，直接返回当前节点的值。
* 若部分重叠，递归查询左右子节点。

=== 更新操作 ===
更新位置<math>i</math>的值时，从叶子节点向上更新所有受影响的父节点。

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

=== 实际案例 ===
'''问题'''：给定一个数组，支持以下操作：
1. 查询区间<math>[l, r]</math>的和。
2. 将区间<math>[l, r]</math>的所有元素增加<math>\Delta</math>。

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

<syntaxhighlight lang="python">
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)
</syntaxhighlight>

== 复杂度分析 ==
* '''构建'''：<math>O(n)</math>。
* '''查询/更新'''：<math>O(\log n)</math>。
* '''空间'''：<math>O(n)</math>（实际分配空间通常为<math>2^{\lceil \log_2 n \rceil + 1}</math>）。

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

{{Stub}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:高级数据结构]]