前缀和代码解析

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

一维

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--;}
}

 运行结果: