算法详解：前缀和技巧及其应用

算法详解：前缀和技巧及其应用

引用

CSDN

1.

https://m.blog.csdn.net/release_lonely/article/details/144376943

前缀和是一种常用的算法技巧，主要用于快速计算数组中某一段区间的和。相比于传统的遍历累加方法，前缀和能够显著减少重复计算，将时间复杂度从O(n)降低到O(1)。

一维前缀和

前缀和的定义是：f[i]代表下标i之前的所有数的和（不包括i）。基于这个定义，我们可以发现区间[n, m]的和可以表示成f[m + 1] - f[n]。这样，有了f数组后，我们就可以在O(1)的时间开销下求出任意区间的和。

f数组的初始化也很简单，可以总结为：
f[i] = f[i - 1] + nums[i - 1], (f[0] = 0, i >= 1)

下面是具体的代码实现：

public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 5, 6, 7};
    int[] f = new int[nums.length + 1];//前缀和数组
    //初始化f
    f[0] = 0;
    for(int i = 1; i <= nums.length; i++) {
        f[i] = f[i - 1] + nums[i - 1];
    }
    
    //查询操作
    Scanner in = new Scanner(System.in);
    int n = in.nextInt(), m = in.nextInt();
    int res = query(n, m);
}
public static int query(int n, int m, int f) {
    return f[m + 1] - f[n];
}  

二维前缀和

在某些问题中，我们可能需要对矩阵进行操作，这时就需要用到二维前缀和。为了方便讲解，我们假设矩阵的开始节点是（1，1）。

二维前缀和f[x][y]代表从矩阵的左上顶点到右下顶点（x，y）的和。假设有这样一个场景：存在一个填充着数字的矩阵matrix[][]，现在需要你求左上顶点o1(x1, y1)到右下顶点o2(x2, y2)这个小矩阵的和。

利用前缀和的思想，我们可以将大矩阵减去一些小矩阵来得到目标矩阵的和。具体来说，我们可以通过整个块（x2，y2）减去红色(包括黄色)、黄色、绿色（包括黄色）的块来得到蓝色块的和。

整个块：f[x2][y2]
黄色：f[x1-1][x2-1]
红色：f[x2][y1-1]
绿色：f[x1 - 1][y2]

因此，蓝色块的和为：f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]

接下来，我们来看如何计算f[][]数组：

f[x][y] = f[x][y - 1] + f[x - 1][y] + matrix[x][y] - f[x - 1][y - 1]

下面是具体的代码实现：

public static void main(String[] args) {
    int[][] nums = {{0, 1, 2, 3, 4, 5, 6, 7}, {0, 1, 2, 3, 4, 5, 6, 7}, {0, 1, 2, 3, 4, 5, 6, 7} ,{0, 1, 2, 3, 4, 5, 6, 7}};
    int[][] f = new int[nums.length + 1][nums[0].length + 1];
    //因为我们下标从1开始所以要特殊处理第0列和行
    for(int i = 0; i < nums.length; i++) {
        f[i][0] = 0;
    }
    for(int j = 0; j < nums[0].length; j++) {
        f[0][j] = 0;
    }
    for(int i = 1; i <= nums.length; i++) {
        for(int j = 1; j <= nums[0].length; j++) {
            f[i][j] = f[i - 1][j] + f[i][j - 1] + nums[i][j] - f[i - 1][j - 1];
        }
    }
    //
    Scanner in = new Scanner(System.in);
    int x1, x2, y1, y2;
    x1 = in.nextInt();
    y1 = in.nextInt();
    x2 = in.nextInt();
    y2 = in.nextInt();
    int res = query(x1, y1, x2, y2, f);
}
public static int query(int x1, int y1, int x2, int y2, int[][] f) {
    return f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}