前缀和是指数组一定范围的数的总和,常见的有两种,一维和二维,我会用两道题来分别解析

一维

DP34 【模板】前缀和

题目:

题目解析:

暴力解法

直接遍历数组,遍历到下标为 l 时,开始进行相加,直到遍历到下标为 r ,最后返回总和.这样做的时间复杂度为: O(n)

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        //接收数据
        int n = in.nextInt(),q=in.nextInt();
        int[] arr = new int[n+1];
        arr[0]=0;
        for(int i=1;i<=n;i++){
            arr[i]=in.nextInt();
        }
        while(q>0){
            int l=in.nextInt(),r=in.nextInt();
            int sum = 0;
            for(int i =l;i<=r;i++){
                sum+=arr[i];
            }
            System.out.println(sum);
            q--;
        }
    }
}

虽然代码本身是没有问题的,但是在某些情况下会运行超时

优化

对于前缀和来说,我们可以使用动态规划的部分知识来进行解决,总共分为两步

1.预处理前缀和数组

我们创建一个新的数组,数组的规模和原数组保持一致,如图:

 

但是在我们求dp数组时,难免会对原数组重复计算,这样会增加代码的耗时,有没有简洁的方法呢?

当然是有的,从dp的获得式中我们可以发现, dp[i] = dp[i-1]+arr[i] 

2.使用数组

最后我们就可以返回值, 也就是上文提到的 dp[r]-dp[l-1] 

代码

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // 注意 hasNext 和 hasNextLine 的区别
    //接收数据
    int n = in.nextInt(),q=in.nextInt();
    int[] arr = new int[n+1];
    arr[0] = 0;
    for(int i=1;i<arr.length;i++){
        arr[i] = in.nextInt();
    }
    //计算动态数组
    long[] dp = new long[n+1];
    dp[0] = 0;
    for(int i=1;i<dp.length;i++){
        dp[i]=dp[i-1]+arr[i];
    }
    //处理结果
    while(q>0){
        int l=in.nextInt(),r=in.nextInt();
        System.out.println(dp[r]-dp[l-1]);
        q--;
    }
}

在代码中我们可以看到,我们为数组增加了辅助节点,也就是 arr[0] 和 dp[0] ,那么为什么要增加这个辅助节点呢?或者为什么在使用数组的时候,下标要从1开始计算呢?

因为如果我们没有辅助节点或者从0开始计算,那么当 l (求前缀和的起点) 为 0 时,那么 dp[l-1] 就会越界

运行结果

二维

二维数组也就是矩阵,在计算矩阵的前缀和时,我们需要更注意一些细节

例题: DP35 【模板】二维前缀和

这道题大致与上一道题相似,所以就不进行暴力解法了,直接开始解析

也就是说,这里我们已经得到了用于动态规划的数组 dp ,我们只要再将dp中的值进行计算,就可以得到最后的值了

所以,最后要得出的答案就是 D = dp[x2][y2] -dp[x1-1][y1] -dp[x1][y1-1] +dp[x1-1][y1-1] 

代码:

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // 注意 hasNext 和 hasNextLine 的区别
    //获取数据
    int n = in.nextInt(),m=in.nextInt(),q=in.nextInt();
    int[][] arr = new int[n+1][m+1];
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            arr[i][j] = in.nextInt();
        }
    }

    //设置动态矩阵
    long[][] dp = new long[n+1][m+1];
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            dp[i][j] = dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1];
        }
    }
    //得出答案
    while(q>0){
        int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();
        System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
        q--;
    }
}

 运行结果: