前缀和

什么是前缀和

简单来说：我们有一个数组x和它的前缀和数组y，他们满足以下公式。
y ₀ = x ₀
y ₁ = x ₀ + x ₁
y ₂ = x ₀ + x ₁ + x ₂
...
即 y[n]=x[1]+x[2]+...+x[n]。
下面是一个实际例子：

\	0	1	2	4	5	6	...
x	1	2	3	4	5	6	...
y	1	3	6	10	15	21	...

得到的结果就是一维前缀和

一维前缀和

一维前缀和的得到很简单，也很好理解，上面的例子就是一维前缀和。
我们只需要遍历的时候一直把之前计算的和 加上自己就能得到当前的和。

 /**
     * 一维前缀和
     *
     * @param src 原数组
     * @return 一维前缀和
     */
    private int[] oneDimen(int[] src) {
        int[] result = new int[src.length];
        for (int i = 0; i < result.length; i++) {
            if (i == 0) {
                result[i] = src[i];
            } else {
                result[i] = result[i - 1] + src[i];
            }
        }
        return result;
    }

那既然我们了解了一维前缀和，那必然会有二维前缀和

二维前缀和

先上一张图，看图就知道是个什么逻辑了。

图一

前缀和数组里每一个位置都表示原数组当前index左上方的数字的和。
比如像图里面画的：prefixSum[3, 3] = src[0~2, 0~2]的和;
二维前缀和数组要怎么计算出来呢？
可以分为四种情况

1. i==0 && j==0，只有一个直接赋值即可：prefixSum[0, 0] = src[0, 0]。
2. i==0，最左边的一排，图中黄色部分，prefixSum[0, j] = prefixSum[0, j-1] + src[0, j]；
3. j==0，最上面一排，途中红色部分，prefixSum[i, o] = prefixSum[i-1, 0] + src[i, 0];
4. i!=0 || j!=0，图中绿色部分，prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] + src[i][j] - prefixSum[i - 1][j - 1];

具体讲第四步：

图二
我们要得到prefixSum[2,2]，我们知道应该是图一中箭头指向的区域。也就是9个方框加起来的和，也就是54。
看图二，我们可以利用prefixSum[1, 2]和prefixSum[2, 1]，但是他俩的区域是重合的，如图二所示，重合的区域又恰好是prefixSum[1, 1]负责的区域，相当于加了两份，需要减掉一份。
所以prefixSum[2,2] = prefixSum[1, 2] + prefixSum[2, 1] - prefixSum[1, 1] + src[2, 2];
也就是54 = 33 + 21 -12(这个是prefixSum[1, 1]) +12(这是src[2, 2])

代码表示：

    /**
     * 二维前缀和
     *
     * @param src 原数组
     * @return 二维前缀和
     */
    private int[][] twoDimen(int[][] src) {
        int[][] result = new int[src[0].length][src.length];
        for (int i = 0; i < src.length; i++) {
            for (int j = 0; j < src[0].length; j++) {
                if (i == 0 && j == 0) {//第0个，最左上角
                    result[i][j] = src[i][j];
                } else if (i == 0) {//第一行，最顶部一行
                    result[i][j] = result[i][j - 1] + src[i][j];
                } else if (j == 0) {//第一列，最左边一列
                    result[i][j] = result[i - 1][j] + src[i][j];
                } else {//其他
                    result[i][j] = result[i - 1][j] + result[i][j - 1] + src[i][j] - result[i - 1][j - 1];
                }
            }
        }
        return result;
    }

前缀和的应用

例题1

输入n个数的数列，所有相邻m数的和有n-m+1个，求其中的最小值。
比如：
数组为：[10, 4, 1, 5, 5, 2]
m为：3
结果为：10

/**
     * 获取最小值
     *
     * @param src 原数组
     * @param m   几个
     * @return 最小值
     */
    private int minM(int[] src, int m) {
        if (m <= 0) {
            return 0;
        }
        int[] prefixSum = new int[src.length];
        for (int i = 0; i < prefixSum.length; i++) {
            if (i == 0) {
                prefixSum[i] = src[i];
            } else {
                prefixSum[i] = prefixSum[i - 1] + src[i];
            }
        }
        int first = prefixSum[m - 1], result = first;
        for (int i = m; i < prefixSum.length; i++) {
            int current = prefixSum[i] - prefixSum[i - m];
            result = current > result ? result : current;
        }

        return result;
    }