St表的概念与使用

2024-05-24

ST表查找极值或找出区间修改数值

概念与示例代码

ST表（Sqrt-Table）或Segment Tree（区间树）是一种数据结构，用于高效地处理区间查询和更新问题，特别是在区间最值查询（如最小值、最大值）上表现出色。以下是如何使用ST表的基本步骤：

初始化：首先，你需要一个数组A，其中包含你要处理的原始数据。创建一个大小为4n的辅助数组ST（通常取4n是因为ST表的每个节点存储四个子节点的信息，但这个数量可以因实现方式的不同而变化）。
预处理：使用动态规划的思想，从底向上构建ST表。通常，这涉及递归地将区间划分为较小的部分，并合并这些部分的最值。对于每个节点i，计算其对应区间的最值，例如，如果ST[i]表示区间[l, r]的最值，你可以通过比较子区间[l, m]和[m+1, r]的最值来计算ST[i]，其中m是l和r的中点。
```
def build_ST(A, ST, l, r, i):
    if l == r:
        ST[i] = A[l]
    else:
        mid = (l + r) // 2
        build_ST(A, ST, l, mid, 2 * i + 1)
        build_ST(A, ST, mid + 1, r, 2 * i + 2)
        ST[i] = max(ST[2 * i + 1], ST[2 * i + 2])
```

查询：要查询区间[ql, qr]的最值，从根节点开始，按照倍增策略向下遍历ST表。每次比较当前节点的两个子节点所覆盖的子区间，选择包含目标区间的那个子节点继续查询。

def query_ST(ST, l, r, ql, qr, i):
    if l > qr or r < ql:
        return float('-inf')  # 返回无效值
    if l >= ql and r <= qr:
        return ST[i]
    mid = (l + r) // 2
    return max(query_ST(ST, l, mid, ql, qr, 2 * i + 1),
               query_ST(ST, mid + 1, r, ql, qr, 2 * i + 2))

更新：如果需要修改数组A中的某个元素，同样从根节点开始，找到影响的区间并更新ST表中的相应节点。更新通常涉及到重新计算受影响节点及其子节点的最值。
优化：在实际应用中，为了节省空间，ST表可以进行压缩，比如使用lazy propagation（惰性更新）来延迟一些更新操作，直到它们真正需要时才执行。
示例代码解析
def build_ST(A, ST, l, r, i): 定义一个名为build_ST的函数，接受五个参数：原始数组A，ST数组ST，以及区间边界l、r和节点索引i。
if l == r: 判断当前区间是否只有一个元素，即l等于r。这是构建过程的终止条件，因为一个元素的区间最值就是该元素本身。
ST[i] = A[l] 如果当前区间只包含一个元素，那么将该元素的值赋给ST表的当前节点ST[i]。
else: 如果当前区间包含多个元素，需要进一步划分区间。
mid = (l + r) // 2 计算当前区间的中间索引mid，用于将区间划分为左右两半。
build_ST(A, ST, l, mid, 2 * i + 1) 递归调用build_ST，处理左半部分区间[l, mid]，并将新的左边界l、新的右边界mid和左子节点的索引2 * i + 1传递给函数。
build_ST(A, ST, mid + 1, r, 2 * i + 2) 同样，递归调用build_ST，处理右半部分区间[mid + 1, r]，并将新的左边界mid + 1、新的右边界r和右子节点的索引2 * i + 2传递给函数。
ST[i] = max(ST[2 * i + 1], ST[2 * i + 2]) 当处理完左右两个子区间后，计算这两个子区间的最值，将结果存储在当前节点ST[i]。这里假设我们正在构建一个求最大值的ST表，所以使用max函数。如果是求最小值，应使用min函数。

这个函数通过递归地划分区间并合并子区间的结果，构建了ST表。当所有递归调用完成时，ST数组就代表了一个完整的ST表，可用于区间查询。

St表的概念与使用

ST表查找极值或找出区间修改数值

概念与示例代码

示例代码解析