[数据结构与算法]前缀和：空间换时间的技巧

LeetCode 例题精讲 | 18 前缀和：空间换时间的技巧

????????在设计算法时，时间复杂度始终是我们关注的重点。我们需要让算法的时间复杂度尽可能低，追求运行效率。有些时候，我们可以通过增加空间占用的方式减少算法的运行时间，这便是空间换时间。

????????动态规划就是一类空间换时间的算法。动态规划通过保存所有子问题的计算结果，可以避免子问题的重复计算。这种方法的代价是?DP 数组?占用了较多的空间。

????????前缀和同样也是一种空间换时间的技巧，只不过我们使用的不是 DP 数组，而是「前缀和数组」。

?

?

?利用前缀和求i到j的和：sumRange(i,?j)?=?preSum[j+1]?-?preSum[i]（左闭右开）（就是说，j+1是索引到j的和，? i是索引到i-1的和）

class NumArray {
    
    private int[] preSum;

    // 预处理阶段
    public NumArray(int[] nums) {
        int n = nums.length;
        // 计算前缀和数组
        preSum = new int[n+1];
        preSum[0] = 0;
        for (int i = 0; i < n; i++) {
            preSum[i+1] = preSum[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return preSum[j+1] - preSum[i];
    }
}

如果前缀和数组的定义中不使用左闭右开区间，如何利用前缀和数组求区间的和呢？

preSum[j]-preSum[i-1];(但是i-1可能会越界！)

前缀和 & 差分

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前??项的和”。1

C++ 标准库中实现了前缀和函数?std::partial_sum，定义于头文件?<numeric>?中。