前缀和介绍 – 玩算法

数组的前 n 项和就叫做前缀和，前缀和一般用于快速计算任意一段区间内元素的和，前缀和作为一种常见的预处理方式，主要用于降低时间复杂度，经常用于处理连续的子数组。除了前缀和，还有前缀求余，前缀异或，前缀乘积等。

一维前缀和

一维前缀和主要用来处理一维数组的，为了方便处理，减少一些不必要的判断，一般情况下我们让前缀和的第一项为 0 ，也就是 preSum[0] = 0 ，前缀和的后面几项如下。

preSum[1]=preSum[0]+nums[0];
preSum[2]=preSum[1]+nums[1];
preSum[3]=preSum[2]+nums[2];
……
preSum[n]=preSum[n-1]+nums[n-1];

如果想求某个区间内的元素和，比如闭区间 [i,j] ，可以通过前缀和直接相减，不需要在把区间内的元素一个个相加。

来看下代码：

public class PrefixSum {
    int[] preSum;//前缀和数组。

    public PrefixSum(int[] nums) {
        preSum = new int[nums.length + 1];
        // 计算前缀和。
        for (int i = 0; i < nums.length; i++)
            preSum[i + 1] = preSum[i] + nums[i];
    }

    // 统计闭区间[left,right]内的元素和，这里注意偏移量。
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

二维前缀和

二维前缀和处理的是二维数组，和一维数组类似，只不过相加和相减的时候会有点区别，二维前缀和的计算公式如下，如果原二维数组是 m*n 的矩阵，为了方便计算，前缀和二维数组就是 (m+1)*(n+1) 的矩阵，所以后面是加上 matrix[i – 1][j – 1] 而不是 matrix[i][j] 。

 preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];

相加的时候因为 preSum[i – 1][j] 和 preSum[i][j – 1] 有重叠部分 preSum[i – 1][j – 1] ，所以需要减掉。

求矩形区间和的时候需要知道矩形的左上角和右下角的坐标，比如计算左上角 (a,b) 到右下角 (i,j) 所围成的矩形区间和，公式如下。

preSum[i][j] - preSum[a - 1][j] - preSum[i][b - 1] + preSum[a - 1][b - 1];

相减的时候因为会多减，所以需要加上多减的，如下图所示。

代码如下：

class TwoPrefixSum {
    int[][] preSum;// 二维前缀和数组。

    public TwoPrefixSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 这里为了方便计算，二维数组preSum的宽和高都增加1。
        preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 前缀和公式
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1]
                        - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    // (a, b)是左上角坐标，(i, j)是右下角坐标，他们是原数组的坐标，在二维前缀和数组
    // 中相当于(a+1, b+1)和(i+1, j+1)，所以要注意偏移量。
    public int sumRange(int a, int b, int i, int j) {
        return preSum[i + 1][j + 1] - preSum[a][j + 1]
                - preSum[i + 1][b] + preSum[a][b];
    }
}