枚举技巧-前后缀分解

作者： 作者的头像   姚保富 , 时间：2026-07-13 10:29:51 , 所有人可见, 阅读  64

前后缀分解总结

前后缀分解是线性结构（如数组、字符串等）中一种常见且高效的算法设计技巧。通过预处理序列的前缀信息和后缀信息，我们可以将许多涉及“全局查询”、“排除单点”或“区间划分”的问题，从高复杂度优化至 $\mathcal{O}(n)$ 的时间复杂度。

一、 什么是前后缀分解

前后缀分解的核心思想是：将一个全局问题拆分为“左半部分（前缀）”和“右半部分（后缀）”两个独立子问题分别求解，最后进行合并。

对于一个长度为 $n$ 的序列 $A = [A_1, A_2, \dots, A_n]$： * 前缀（Prefix）：形如 $A[1 \dots i]$ 的子序列，其统计信息通常记录在数组 pre[i] 中。 * 后缀（Suffix）：形如 $A[i \dots n]$ 的子序列，其统计信息通常记录在数组 suf[i] 中。

当我们需要求解关于排除第 $i$ 个元素后的剩余区间信息，或者寻找某个划分点 $i$ 将序列一分为二的最优解时，通过预处理得到的 pre 和 suf 数组，可以实现 $\mathcal{O}(1)$ 的状态合并。

二、 适用场景与典型类型

当前半部分与后半部分独立且易于递推时，前后缀分解能够发挥很好的作用。常见的统计信息包括：

  1. 区间求和/乘积：
    • 前缀和：$pre[i] = pre[i-1] + A[i]$
    • 后缀和：$suf[i] = suf[i+1] + A[i]$
  2. 区间最值（Min / Max）：
    • 前缀最大值：$pre[i] = \max(pre[i-1], A[i])$
    • 后缀最大值：$suf[i] = \max(suf[i+1], A[i])$
  3. 数论属性（如最大公约数 GCD）：
    • 前缀 GCD：$pre[i] = \gcd(pre[i-1], A[i])$
    • 后缀 GCD：$suf[i] = \gcd(suf[i+1], A[i])$
  4. 动态规划状态（Bidirectional DP）：
    • 从左向右递推得到一个 DP 数组，从右向左递推得到另一个 DP 数组，在中间某点进行合并。

三、 经典模板与实现步骤

前后缀分解通常遵循以下三个步骤：

  1. 自左向右线性扫描：递推计算前缀数组 pre。
  2. 自右向左线性扫描：递推计算后缀数组 suf。
  3. 遍历划分点合并求解：枚举分割点 $i$，将 pre[i-1] （或 pre[i]）与 suf[i+1] （或 suf[i]）进行合并，更新全局答案。

通用代码模板

其中merge为一种可合并的操作

// 假设 A 为输入数组，下标从 1 开始
vector<int> pre(n + 2, init\_val);
vector<int> suf(n + 2, init\_val);

// 1. 预处理前缀
for (int i = 1; i <= n; i++) {
    pre[i] = merge(pre[i - 1], A[i]);
}

// 2. 预处理后缀
for (int i = n; i >= 1; i--) {
    suf[i] = merge(suf[i + 1], A[i]);
}

// 3. 合并求解
int ans = default\_ans;
for (int i = 1; i <= n; i++) {
    // 举例：求解排除第 i 个元素后的全局性质
    int cur_val = merge(pre[i - 1], suf[i + 1]);
    ans = update(ans, cur_val);
}

注：为了避免复杂的边界讨论（如 $i-1 < 1$ 或 $i+1 > n$），通常会将 pre 和 suf 数组的大小设为 $n+2$，并合理初始化 pre[0] 和 suf[n+1] 的值（例如求和初始化为 0，求最值初始化为 $\pm\infty$，求 GCD 初始化为 0）。

四、 经典例题解析

例题 1：除自身以外数组的乘积

问题描述：给你一个长度为 $n$ 的整数数组 $nums$，返回输出数组 $answer$，其中 $answer[i]$ 等于 $nums$ 中除 $nums[i]$ 之外其余各元素的乘积，由于答案可能很大，答案对1e9+7取模。

思路分析

由于涉及到取模，不方便使用除法，直接求全局乘积再除以单点是不可行的。由于排除 $nums[i]$ 后，剩余的部分刚好被分成了左半边 $nums[0 \dots i-1]$ 和右半边 $nums[i+1 \dots n-1]$。 这正是前后缀分解的典型应用。

  1. 令 $pre[i]$ 表示前 $i$ 个元素的乘积。
  2. 令 $suf[i]$ 表示从第 $i$ 个元素到末尾的乘积。
  3. 对于每个位置 $i$（下标从 0 开始），除其自身以外的乘积为： $$ans[i] = pre[i-1] \times suf[i+1]$$

复杂度

  • 时间复杂度：$\mathcal{O}(n)$，只需三次线性扫描。
  • 空间复杂度：$\mathcal{O}(n)$，用于存储前缀和后缀乘积。

例题 2：删去一个数使最大公约数（GCD）最大

问题描述：给定一个包含 $n$ 个正整数的数组 $A$，要求删去其中恰好一个数，使得剩下 $n-1$ 个数的最大公约数最大。求这个最大的最大公约数。

思路分析

若暴力枚举删去哪个数，再对剩余的 $n-1$ 个数求 $\text{GCD}$，时间复杂度为 $\mathcal{O}(n^2 \log C)$，在 $n \ge 10^5$ 时会超时。

利用前后缀分解： 1. 定义 $pre[i] = \gcd(A_1, A_2, \dots, A_i)$。 2. 定义 $suf[i] = \gcd(A_i, A_{i+1}, \dots, A_n)$。 3. 当删去第 $i$ 个数时，剩余数的最大公约数即为： $\text{GCD}_{\text{exclude } i} = \gcd(pre[i-1], suf[i+1])$

例题 3：接雨水（Trapping Rain Water）

问题描述：给定 $n$ 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路分析

对于任意位置 $i$ 的柱子，它能承载的雨水高度取决于它左边最高柱子和右边最高柱子的较小值，再减去当前柱子本身的高度。

即：$\text{Water}[i] = \max(0, \min(\text{LeftMax}[i], \text{RightMax}[i]) - height[i])$

这引导我们进行前后缀分解： 1. 前缀分解：自左向右维护一个前缀最大值数组 $pre[i] = \max(pre[i-1], height[i])$。 2. 后缀分解：自右向左维护一个后缀最大值数组 $suf[i] = \max(suf[i+1], height[i])$。 3. 最后遍历每个位置 $i$，累加 $\min(pre[i], suf[i]) - height[i]$ 即可。

五、 与其他算法的对比

维度 / 方法 前后缀分解 线段树 / 树状数组 双指针 / 滑动窗口
时间复杂度 $\mathcal{O}(n)$ $\mathcal{O}(n \log n)$ 预处理，单次查询 $\mathcal{O}(\log n)$ $\mathcal{O}(n)$
空间复杂度 $\mathcal{O}(n)$ （可优化至常数） $\mathcal{O}(n)$ （常数较大） $\mathcal{O}(1)$
适用场景 离线、单点排除、二分区间合并 在线修改、区间动态查询 具有单调性的连续子区间问题
实现难度 较低（简单线性递推） 较高（涉及建树、修改、查询） 中等

小结

前后缀分解是一种极具性价比的优化技巧。它不依赖于复杂的数据结构，仅通过两次简单的线性扫描（方向相反）收集上下文信息，便能在涉及“排除单点”或“区间划分”的静态查询问题中，将时间复杂度降低一个维度。掌握这一思想，有助于我们在面对较大数据范围时，快速设计出时间和空间均高效的算法方案。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com