前缀和介绍

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];

来看下代码：

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];
    }
}