算法——前缀和

        如果我们想要得到数组中一段区间的和最朴素的想法肯定是我们从区间的开始下标遍历到结束下标并累加，但是这显然存在一个问题，时间开销是O（n）的级别，并且有着大量的重复计算，求[n, m]的和后继续求[n…m…p]区间和，但是我们还是需要从n开始遍历而不是利用我们之前算过的结果，前缀和就可以帮我们减少重复计算。

一维前缀和

前缀和的定义：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] = 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];
}

原文地址：https://blog.csdn.net/release_lonely/article/details/144376943

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！