前缀和与差分

什么是前缀和？

一维数组前缀和

例如数组nums = [1,2,3,4,5]

则其前缀和数组为qian = [1,3,6,10,15]，即qian数组的i索引位置处的值为nums数组索引0-i值的和

则有如下关系：nums[i] = qian[i] - qian[i-1]

注：使用该方法有一最大优势便是可以以(O1)的时间复杂度得到某块区间的总和，是典型的牺牲空间换取时间

二维数组前缀和

二维数组的应用和计算

二维数组前缀和是一种在二维矩阵上进行快速区域求和的技术，它是一维前缀和概念的扩展。在二维数组中，前缀和可以帮助我们快速计算任意子矩阵的元素和，这在处理图像处理或者某些区域查询问题时非常有用。

二维前缀和的定义

二维前缀和是指对于一个给定的二维数组a，我们构建一个新的二维数组sum，其中sum[i][j]表示从a[0][0]到a[i][j]所有元素的和。这样sum数组的每个元素都代表了一个矩形区域内元素的总和。

计算二维前缀和

计算二维前缀和的过程可以通过动态规划的方式来完成。对于数组a中的每个元素a[i][j]，我们可以根据以下公式来计算sum[i][j]

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]

使用二维前缀和求子矩阵和

一旦我们计算出了二维前缀和数组sum，我们就可以快速求出任意子矩阵的和。假设我们要求从(x1, y1)到(x2, y2)形成的子矩阵的和，我们可以使用以下公式

subSum = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class PrefixSum {
    public static int[][] getPrefixSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 创建一个新的二维数组用于存储前缀和
        int[][] prefixSum = new int[m][n];

        // 计算第一行的前缀和
        prefixSum[0][0] = matrix[0][0];
        for (int j = 1; j < n; j++) {
            prefixSum[0][j] = prefixSum[0][j - 1] + matrix[0][j];
        }

        // 计算第一列的前缀和
        for (int i = 1; i < m; i++) {
            prefixSum[i][0] = prefixSum[i - 1][0] + matrix[i][0];
        }

        // 计算其余位置的前缀和
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i][j];
            }
        }

        return prefixSum;
    }
}

差分法

定义

对于已知有n个元素的一维数列nums，我们可以建立记录它与每项与前一项得差值得差分数组f；显然，f[1] = nums[1] - 0 = nums[1]; 对于整数 i∈[2,n]，我们让f[i]=nums[i]-nums[i-1]。将对nums的一些操作转移至f数列，最终合并f得到nums的一种操作，叫做差分法。

举个栗子

  • 例如 nums=[3,4,1,5,6,2,7,9]
  • 即，f=[3,1,-3,4,1,-4,5,-2]
    当我们需要对数组的[1,6]，这个区间的数+1，并求处区间+1后数组的值
  • 此时，我们只需要对f数组的左边界第1项+1，对f数组的右边界第7项-1，此时f=[4,1,-3,4,1,-4,4,2]，因为第一项+1，导致1-6项的差值都+1了，即完成对给定区间进行+1操作

差分法的用途

  • 快速处理区间加减操作
  • 优化时间复杂度，也是典型的牺牲空间换时间
  • 对数组f求前缀和即可得到原数组nums

代码实现

对给定数组求差分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main{
    public static int[] getDifferenceArray(int[] arr) {
        int n = arr.length;
        int[] diffArray = new int[n];

        diffArray[0] = arr[0];
        for (int i = 1; i < n; i++) {
            diffArray[i] = arr[i] - arr[i - 1];
        }

        return diffArray;
    }
}

对给定数组求差分数组后通过前缀和得到原数组

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main{
    public static int[] getArray(int[] diffArray) {
        int n = diffArray.length;
        int[] originalArray = new int[n];

        originalArray[0] = diffArray[0];
        for (int i = 1; i < n; i++) {
            originalArray[i] = originalArray[i - 1] + diffArray[i];
        }

        return originalArray;
    }
}