一维前缀和idea

MrHe··3 min read

一维前缀和

1. 问题场景：为什么要用前缀和？

我们从一个最简单的需求开始。想象一下，我给你一个数组 nums，然后我会反复地问你同一个问题：“请告诉我，nums 数组从下标 L 到 R 的所有元素的和是多少？”

暴力解法： 这个需求太简单了。你可能会想，这不就是写个 for 循环嘛！来一个查询 (L, R)，我就从 L 遍历到 R，把所有 nums[i] 加起来。

// 暴力解法
int sum = 0;
for (int i = L; i <= R; i++) {
    sum += nums[i];
}
return sum;

复杂度分析： 这个方法当然是正确的。但是，如果数组的长度是 N，那么每次查询的时间复杂度最坏是 O(N)（当 L=0, R=N-1 时）。如果我有 M 次查询，总的时间复杂度就是 O(M * N)。 在算法竞赛或者实际工程中，如果 N 和 M 都是 10^5 量级，那 10^5 * 10^5 = 10^10，这台计算机跑到冒烟也算不完，肯定超时了。

思路演进： 我们来分析一下暴力解法慢在哪里。它慢在重复计算。 比如，我问你 sum(0, 50)，你加了一遍。我再问你 sum(0, 51)，你又把 0 到 50 的部分重新加了一遍，这太浪费了！ 我们能不能提前“预处理”一些信息，让每次查询都变得飞快？

答案是可以的！这就是前缀和思想的来源。

2. 前缀和的原理

核心定义： 我们创建一个新的数组，叫前缀和数组，我们叫它 preSum。 preSum[i] 的定义是：原始数组 nums 从下标 0 开始，一直累加到下标 i 的和。 preSum[i] = nums[0] + nums[1] + ... + nums[i]

这个 preSum 数组我们可以在 O(N) 的时间内一次性计算出来： preSum[0] = nums[0] preSum[i] = preSum[i-1] + nums[i] (for i > 0)

如何使用 preSum 数组进行查询？ 有了这个神器，计算 sum(L, R) 就变得异常简单了。 sum(L, R) = nums[L] + ... + nums[R] 这不就等于： (nums[0] + ... + nums[R]) - (nums[0] + ... + nums[L-1]) 吗？

这正好就是： preSum[R] - preSum[L-1]

结论（核心公式）: sum(L, R) = preSum[R] - preSum[L-1]

特殊情况：如果 L=0 呢？L-1 就越界了。此时 sum(0, R) 就是 preSum[R] 本身。

一个更骚的技巧 (OI/ACM 风格) 为了避免对 L=0 进行 if-else 的特殊判断，我们可以让 preSum 数组的长度比 nums 数组大 1，即 N+1。 我们让 preSum[0] = 0，然后 preSum[i] 存储 nums[0...i-1] 的和。 preSum[i] = nums[0] + ... + nums[i-1]

这样，preSum 的递推公式变为： preSum[i+1] = preSum[i] + nums[i]

而查询 sum(L, R) (nums 数组的下标) 的公式就统一变成了： sum(L, R) = preSum[R+1] - preSum[L]

你看，不管 L 是不是 0，这个公式都成立！非常优雅！

3. OI/ACM 风格代码实现

这个问题就是 LeetCode 的经典入门题。

问题重述 实现 NumArray 类：

  • NumArray(int[] nums) 用数组 nums 初始化对象。

  • int sumRange(int left, int right) 返回数组 nums 中索引 left 到 right 的元素之和（包含 left 和 right）。

/**
 * LeetCode 303. 区域和检索 - 数组不可变
 * OI/ACM 风格实现，采用长度为 N+1 的前缀和数组技巧
 */
class NumArray {
​
    // preSum[i] 存储 nums 数组中 [0...i-1] 的和
    // 这是一个非常经典的技巧，可以避免在查询时处理 L=0 的边界情况
    private int[] preSum;
​
    /**
     * 构造函数：预处理前缀和数组
     * 时间复杂度: O(N), N 为 nums 的长度
     * @param nums 原始数组
     */
    public NumArray(int[] nums) {
        int n = nums.length;

        // 核心技巧：前缀和数组长度为 n + 1
        // preSum[0] = 0, 方便统一查询逻辑
        preSum = new int[n + 1];
​
        // 构建前缀和数组
        // preSum[i+1] = preSum[i] + nums[i]
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
    }
​
    /**
     * 查询区间 [left, right] 的和
     * 时间复杂度: O(1)
     * @param left  区间左边界 (inclusive)
     * @param right 区间右边界 (inclusive)
     * @return 区间和
     */
    public int sumRange(int left, int right) {
        // nums[left...right] 的和
        // 等于 (nums[0...right] 的和) - (nums[0...left-1] 的和)
        // 对应到 preSum 数组中就是 preSum[right+1] - preSum[left]
        return preSum[right + 1] - preSum[left];
    }
}

总结 我们来看一下这个优化的效果：

  • 预处理时间：O(N)，用来构建 preSum 数组。

  • 查询时间：O(1)，每次查询只需要做一次减法。

  • 空间复杂度：O(N)，需要额外的空间存储 preSum 数组。

这种用 O(N) 的预处理和 O(N) 的额外空间，把查询时间从 O(N) 降到 O(1) 的思想，被称为“空间换时间”，是算法优化中非常核心的一种思想。

  • #5ymn57ya5zkm