前缀数组和后缀数组

前缀数组和后缀数组是我刷题时最早学会的一批“省钱”技巧，很多查询看着要循环，存一个前缀和就能 O(1) 出答案。这篇结合 5 个例题，记一下我对这两种技术的理解。

一、前缀数组（Prefix Sum Array）

基本概念

前缀数组说白了就是把从头到每个位置的和（或其他累积结果）提前算好存起来，之后想查任意区间，都是 O(1) 的事。

构建方法

对于一个数组a[0..n-1]，其前缀数组prefix定义为：

• prefix[0] = a[0]
• prefix[i] = prefix[i-1] + a[i] (对于i > 0)

应用场景

1. 快速计算区间和：sum(a[l..r]) = prefix[r] - prefix[l-1]（注意边界条件）
2. 解决子数组相关问题
3. 结合其他算法优化时间复杂度

例题1：简单前缀和（LeetCode 303. 区域和检索 - 数组不可变）

问题描述：给定一个整数数组，多次查询区间和。

解法：

class NumArray {
private:
    vector<int> prefix;
public:
    NumArray(vector<int>& nums) {
        prefix.resize(nums.size()+1, 0);
        for(int i=0; i<nums.size(); ++i) {
            prefix[i+1] = prefix[i] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        return prefix[right+1] - prefix[left];
    }
};

二、后缀数组（Suffix Sum Array）

基本概念

后缀数组跟前缀数组一个思路，只是从数组末尾开始往前累积。

构建方法

对于一个数组a[0..n-1]，其后缀数组suffix定义为：

• suffix[n-1] = a[n-1]
• suffix[i] = a[i] + suffix[i+1] (对于i < n-1)

应用场景

1. 需要从后向前处理的问题
2. 某些特定类型的区间查询
3. 与前缀数组结合解决更复杂问题

例题2：后缀和简单应用

问题描述：计算从每个位置开始到数组末尾的所有元素的和。

解法：

vector<int> calculateSuffixSum(vector<int>& nums) {
    int n = nums.size();
    vector<int> suffix(n);
    suffix[n-1] = nums[n-1];
    for(int i=n-2; i>=0; --i) {
        suffix[i] = nums[i] + suffix[i+1];
    }
    return suffix;
}

三、进阶例题

例题3：中等难度 - 最大子数组和（LeetCode 53. 最大子数组和）

问题描述：找到一个具有最大和的连续子数组。

解法（Kadane算法，可以看作前缀和思想的变种）：

int maxSubArray(vector<int>& nums) {
    int max_sum = INT_MIN;
    int current_sum = 0;
    for(int num : nums) {
        current_sum = max(num, current_sum + num);
        max_sum = max(max_sum, current_sum);
    }
    return max_sum;
}

例题4：中等难度 - 除自身以外数组的乘积（LeetCode 238. 除自身以外数组的乘积）

问题描述：不使用除法，计算数组中每个元素除自身外的乘积。

解法（前缀积+后缀积）：

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, 1);

    // 计算前缀积
    int prefix = 1;
    for(int i=0; i<n; ++i) {
        res[i] = prefix;
        prefix *= nums[i];
    }

    // 计算后缀积并与前缀积相乘
    int suffix = 1;
    for(int i=n-1; i>=0; --i) {
        res[i] *= suffix;
        suffix *= nums[i];
    }

    return res;
}

例题5：较难 - 寻找最小正数缺失（LeetCode 41. 缺失的第一个正数）

问题描述：找到数组中缺失的最小正整数。

解法（利用数组本身作为标记的前缀思想）：

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();

    // 第一次遍历，将数字放到正确的位置上
    for(int i=0; i<n; ) {
        if(nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
            swap(nums[i], nums[nums[i]-1]);
        } else {
            i++;
        }
    }

    // 第二次遍历，找到第一个位置不对的数字
    for(int i=0; i<n; ++i) {
        if(nums[i] != i+1) {
            return i+1;
        }
    }

    return n+1;
}

四、前缀数组和后缀数组的高级应用

1. 二维前缀和

用于快速计算矩阵中子矩阵的和。

构建方法：

vector<vector<int>> buildPrefix2D(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> prefix(m+1, vector<int>(n+1, 0));
    for(int i=1; i<=m; ++i) {
        for(int j=1; j<=n; ++j) {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];
        }
    }
    return prefix;
}

int queryPrefix2D(vector<vector<int>>& prefix, int row1, int col1, int row2, int col2) {
    return prefix[row2+1][col2+1] - prefix[row1][col2+1] - prefix[row2+1][col1] + prefix[row1][col1];
}

2. 差分数组

差分数组就是前缀数组的逆操作，专门用来高效处理区间更新。

构建方法：

vector<int> buildDiffArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> diff(n);
    diff[0] = nums[0];
    for(int i=1; i<n; ++i) {
        diff[i] = nums[i] - nums[i-1];
    }
    return diff;
}

void rangeUpdate(vector<int>& diff, int l, int r, int val) {
    diff[l] += val;
    if(r+1 < diff.size()) diff[r+1] -= val;
}

vector<int> getOriginalArray(vector<int>& diff) {
    vector<int> res(diff.size());
    res[0] = diff[0];
    for(int i=1; i<diff.size(); ++i) {
        res[i] = res[i-1] + diff[i];
    }
    return res;
}

五、总结

前缀数组和后缀数组是我刷区间题时最常用的两个工具，它们能做到：

1. 将许多O(n)的查询操作优化为O(1)
2. 简化复杂问题的解法
3. 与其他算法结合产生更高效的解决方案

掌握这些技术需要：

• 理解其基本原理
• 熟练编写构建和查询代码
• 识别哪些问题可以应用这些技术
• 多做练习，积累经验

这 5 道例题做下来，我对前缀/后缀数组才算真正用熟。比赛里别死记模板，题目一变就得灵活变通，很多时候还要把这两个技术组合起来用。