数组前缀后缀

### 数组前缀和后缀计算的实现方式 #### 前缀和计算 前缀和是一种常见的优化技术，主要用于加速区间查询操作。通过预先计算数组的部分和，可以显著降低时间复杂度。 对于一个长度为 `n` 的数组 `arr`，其前缀和数组 `prefix_sum` 定义如下： ```python def calculate_prefix_sum(arr): prefix_sum = [0] * (len(arr) + 1) for i in range(len(arr)): prefix_sum[i + 1] = prefix_sum[i] + arr[i] return prefix_sum ``` 上述代码中，`prefix_sum[i]` 表示数组 `arr` 中从索引 `0` 到 `i-1` 的累加和[^1]。这种预处理允许我们以 O(1) 时间复杂度完成任何区间的求和操作。 例如，要计算数组 `arr` 中 `[l, r]` 范围内的和，可以通过以下公式得到： \[ \text{sum}(l, r) = \text{prefix\_sum}[r+1] - \text{prefix\_sum}[l] \] --- #### 后缀数组及其应用 后缀数组是一个重要的数据结构，通常用于字符串匹配问题。它表示字符串所有可能的后缀按字典序排列的结果。 以下是构建后缀数组的一个基本实现： ```python def build_suffix_array(s): n = len(s) suffixes = [(s[i:], i) for i in range(n)] suffixes.sort(key=lambda x: x[0]) suffix_array = [suffix[1] for suffix in suffixes] return suffix_array ``` 在此基础上，还可以进一步构造名次数组（Rank Array），即每个后缀在其排序后的排名。两者之间的关系是互逆的，因此可以根据其中之一高效地重建另一个[^2]。 --- #### 结合实例分析 考虑一个问题：如何分割一个数组使其满足特定条件？ 假设有一个非负整数数组 `nums` 和目标数量 `m`，我们需要找到一种划分方案使这些子数组各自和的最大值尽可能小。此问题可通过二分查找配合前缀和技巧解决[^3]。 核心思路在于设定上下界并验证中间值是否可行作为最大子数组和。具体步骤省略此处细节描述。 --- #### 树状数组扩展至前缀最值 除了简单的前缀和外，树状数组还能支持更复杂的查询需求，比如寻找某个范围内的最大/最小值。下面展示了一个基于树状数组维护前缀最大值的例子[^4]: ```python class FenwickTreeMax: def __init__(self, size): self.size = size self.tree = [float('-inf')] * (size + 1) def update(self, idx, value): while idx <= self.size: self.tree[idx] = max(self.tree[idx], value) idx += idx & (-idx) def query_max(self, idx): result = float('-inf') while idx > 0: result = max(result, self.tree[idx]) idx -= idx & (-idx) return result ``` 该类提供了更新单点以及查询指定位置之前所有元素最大值的功能。 ---