devbox
正经夜光杯
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

前缀与差分（java版）模板代码+题目_一维前缀和java代码

作者：正经夜光杯 | 2024-07-23 20:49:24

赞

踩

一维前缀和java代码

 前言

大家好，本文主要讲解的是一维，二维前缀与差分的使用，重点掌握公式，理解其用法。此外，小编水平有限，如果有错误的地方，还请多多指正。那么正文就开始啦  

目录

​一维前缀和 

如何求一维前缀和：

​二维前缀和

如何求二位前缀和

​一维差分

​二维差分

​练习题

 习题1(一维前缀和)

练习题2（二维前缀和）

练习题3（一维差分）

总结

一维前缀和 

问题引入

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l,r。对于每个询问，输出原序列中从第1个数到第r个数的和。

定义：S[i]为数组中1~i的总和，即s[i] = a[1] + a[2] + ... + a[i];（数组从1开始存值）

如何求一维前缀和：

核心代码

  1. for(int i = 1; i <= n; i++)
  2. {
  3.     s[i] = s[i-1] + a[i]; //0~i-1的总和加上第i个数
  4. }

注意：这里的i是从1开始，如果i是从0开始，s[i] = s[i-1] + a[i-1]（写起来比较方便）

完整代码 

  1. import java.util.Scanner;
  2.  
  3. public class 求前缀和
  4. {
  5.     static int n; //数组长度
  6.     static int m; //询问次数
  7.     static int a[] = new int[100010]; //定义一个数组
  8.     static int s[] = new int[100010]; //前缀和数组
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt(); m = sc.nextInt();
  12.         for(int i = 1; i <= n; i++)
  13.         { //读入数组
  14.             a[i] = sc.nextInt();
  15.         }
  16.         for (int i = 1; i <= n; i++) {
  17.             s[i] = s[i - 1] + a[i]; //0~i的和
  18.         }
  19.         while(m-- != 0)
  20.         {
  21.             int l = sc.nextInt(), r = sc.nextInt();
  22.             int ans = s[r] - s[l - 1];
  23.             System.out.println(ans);
  24.         }
  25.     }
  26. }

二维前缀和

 

问题引入：

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

定义：s[i]][j]为左上坐标为(1,1), 右下坐标为(i , j)的矩阵和（数组从(1,1)开始存储）

如何求二位前缀和

核心代码：

  1. for(int i = 1; i <= n; i++)
  2. {
  3.     for(int j = 1; j <= m; j++)
  4.     {
  5.         s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
  6.     }
  7. }

完整代码

  1.  
  2. import java.util.Scanner;
  3.  
  4. public class 二维前缀和
  5. {
  6.     static int n, m; //分别代表矩阵行数，列数
  7.     static int[][] a = new int[1010][1010];//二维数组
  8.     static int[][] s = new int[1010][1010];//二维前缀和数组
  9.  
  10.     public static void main(String[] args)
  11.     {
  12.         Scanner sc = new Scanner(System.in);
  13.         n = sc.nextInt(); m = sc.nextInt();
  14.         for(int i = 1; i <= n; i++) //输入二维矩阵
  15.         {
  16.             for(int j = 1; j <= m; j++)
  17.             {
  18.                 a[i][j] = sc.nextInt();
  19.             }
  20.         }
  21.  
  22.         //输出二维前缀和矩阵
  23.         for(int i = 1; i <= n; i++)
  24.         {
  25.             for(int j = 1; j <=m; j++)
  26.             {
  27.                 s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]; //求二维数组前缀和公式
  28.                 System.out.print(s[i][j] + " ");
  29.             }
  30.             System.out.println(); //换行输出
  31.         }
  32.     }
  33. }

还可以进行q次查询，在核心代码处加个while循环即可。

  • 查询为 O(1)

  • 总时间复杂度：O(n*m+q)

一维差分

 

问题引入

输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l,r,c，表示将序列中[l,r]之间的每个数加上c。

最后输出进行完所有操作后的序列。（1 <= n, m <= 100000）

差分定义：b[i] = a[i] - a[i-1], 即b[i]为第i个数与第i-1个数的差值（数组从1开始存）

特性：a[i] = b[1]+b[2]+ ... +b[i]（前缀和）

那对a数组中[l,r]之间的每个数加上c对b数组的影响是怎样的呢？

 

  1. import java.util.Scanner;
  2.  
  3. public class 一维差分
  4. {
  5.     static int n; //数组长度
  6.     static int m; //询问次数
  7.     static int a[] = new int[100010]; //定义一个数组
  8.     static int b[] = new int[100010]; //前缀和数组
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt(); m = sc.nextInt();
  12.         for(int i = 1; i <= n; i++)
  13.         { //读入数组
  14.             a[i] = sc.nextInt();
  15.         }
  16.         for (int i = 1; i <= n; i++) {
  17.             b[i] = a[i] - a[i-1]; //求得的差分值赋给b数组
  18.         }
  19.         while(m-- != 0)
  20.         {
  21.             int l = sc.nextInt(),r = sc.nextInt(), c = sc.nextInt(); //在a数组l和r之间的每个数都加上c
  22.             b[l] += c; b[r+1] -= c; // 对b数组的影响就是这样
  23.             for(int i = 1; i <= n; i++)
  24.             {
  25.                 b[i] += b[i-1]; //求b数组前缀和，结果就是a[i]的值
  26.             }
  27.             for(int i = 1; i <= n; i++)
  28.             {
  29.                 System.out.print(b[i] + " "); //输出的结果就是增加后的a数组（l与r之间加上了c值）
  30.             }
  31.         }
  32.     }
  33. }

  • 询问O(1)

  • 时间复杂度：O(n+m)

二维差分

 

问题引入

输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1,y1,x2,y2,c, 其中(x1,y1)和(x2,y2)表示，一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。

最后将进行完所有操作后的矩阵输出（1 <= n, m<= 1000, 1 <=q <= 200000）

定义：a[i][j] = a[1][1]+ b[1][2]+ ... + b[i][j]((1,1)到(i,j)的矩阵和)（b为差分矩阵）

注意：根据一维差分的特性，二维差分也必定需要用到前缀和，但这里我们不能像一位那样先推出差分数组，而是利用修改操作得到差分矩阵。

 

 初始差分矩阵：b数组初始化为0，进行左上为(i,j), 右下为(i,j)，右下为(i,j) 矩阵添加c[i][j]的修改操作

  1. for(int i = 1; i <= n; i++)
  2. {
  3.     for(int j = 1; j <= m; j++)
  4.     {
  5.         b[i][j] += c[i][j];
  6.         b[i+1][j] -= c[i][j];
  7.         b[i][j+1] -= c[i][j];
  8.         b[i+1][j+1] += c[i][j];
  9.     }
  10. }

完整代码

  1. import java.util.Scanner;
  2.  
  3. public class 二维差分 {
  4.     static int n; //数组行数
  5.     static int m; //询问列数
  6.     static int a[][] = new int[1010][1010]; //定义二维数组
  7.     static int b[][] = new int[1010][1010]; //二维差分数组
  8.     public static void main(String[] args) {
  9.         Scanner sc = new Scanner(System.in);
  10.         n = sc.nextInt(); m = sc.nextInt(); int c = sc.nextInt();
  11.         for(int i = 1; i <= n; i++)
  12.         { //读入数组
  13.             for(int j = 1; j <= m; j++)
  14.             {
  15.              a[i][j] = sc.nextInt();
  16.             }
  17.         }
  18.         //初始化差分矩阵
  19.         for(int i = 1; i <= n; i++)
  20.         {
  21.             for(int j = 1; j <= m; j++)
  22.             {
  23.                 b[i][j] += c;
  24.                 b[i+1][j] -= c;
  25.                 b[i][j+1] -= c;
  26.                 b[i+1][j+1] += c;
  27.             }
  28.         }
  29.         //求二维前缀和
  30.         for(int i = 1; i <= n; i++)
  31.         {
  32.             for(int j = 1; j <=m; j++)
  33.             {
  34.                 b[i][j] = b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];
  35.             }
  36.         }
  37.         for(int i = 1; i <= n; i++)
  38.         {
  39.             for(int j = 1; j <=m; j++)
  40.             {
  41.                 System.out.print(b[i][j] + " ");
  42.             }
  43.             System.out.println();
  44.         }
  45.     }
  46. }

练习题

 习题1(一维前缀和)

题目

蓝桥杯 2022 省赛 A 组 C 题

 思路

本题如果用常规方法，双重for循环遍历数组，时间复杂度为 O(n2)，如果运用些数学知识，例如前缀和，只用一个for循环即可完成求解，时间复杂度为 O(n)，运用一维前缀和，我们求出数组的和(sum)后，在遍历求和时，依次减去当前索引所指的数，再与这个被减的数相乘，就可以得到本题的答案。

完整代码

  1. import java.util.Scanner;
  2.  
  3. public class 求和 {
  4.     public static void main(String[] args)
  5.     {
  6.         Scanner sc = new Scanner(System.in);
  7.         int n = sc.nextInt(); //数组长度
  8.         Long[] a = new Long[n]; //定义一个数组
  9.         Long sum = 0l; //总和初始化为0
  10.         for (int i = 0; i < a.length; i++)
  11.         {
  12.             a[i] = sc.nextLong();//读入数组
  13.             sum += a[i]; //求前缀和
  14.         }
  15.         Long res = 0l; //存放答案
  16.         for(int i = 0; i < a.length; i++)
  17.         {
  18.             sum -= a[i]; 
  19.             res += sum*a[i]; //求总和
  20.         }
  21.         System.out.println(res);
  22.         sc.close();
  23.     }
  24. }

练习题2（二维前缀和）

激光炸弹

 思路

这是一道二维前缀和的经典题型，题目要求边上的不能算上，所以我们处理边长-R的前缀和即可。最终求出最优爆炸范围，我们先求出前缀和，也就是总的范围，然后减去R*R的范围，也就是不能爆炸的范围，就得到了被爆炸的范围，具体画图一下比较好理解。

  1. import java.util.Scanner;
  2.  
  3. public class 激光炸弹
  4. {
  5.     static int n,R; //分别表示n行(n个目标)，边长为R的正方形
  6.     static int[][] a = new int[5010][5010]; //原矩阵
  7.     static int[][] s = new int[5010][5010]; //二维前缀和矩阵
  8.  
  9.     public static void main(String[] args)
  10.     {
  11.         Scanner sc = new Scanner(System.in);
  12.         int n = sc.nextInt(),R = sc.nextInt();
  13.         for(int i = 1; i <= n; i++)
  14.         {
  15.             int x = sc.nextInt(), y = sc.nextInt(), v = sc.nextInt();
  16.             a[x+1][y+1] += v;//注意：数组会越界，所以坐标x，y都要加1；这道题目坐标从0开始，但我们从1开始处理
  17.         }
  18.         //求前缀和
  19.         for(int i = 1; i <= 5001; i++)
  20.         {
  21.             for(int j = 1; j <= 5001; j++)
  22.             {
  23.                 s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
  24.             }
  25.         }
  26.         R = Math.min(R,5001);
  27.         long max = 0;
  28.         for(int i = R; i <= 5001; i++)
  29.         {
  30.             for(int j = R; j <= 5001; j++)
  31.             {
  32.                 max=Math.max(max,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
  33.             }
  34.         }
  35.         System.out.println(max);
  36.     }
  37. }

练习题3（一维差分）

积木大赛

 思路

这道题思路还是比较简单的，简单画个草图就能差不多看出来，要在连续区间内建造积木，就想到了差分，如果下一栋积木比上一栋高，差分出来为正，就是我们需要建造的，反之，如果下一栋积木比上一栋积木矮，为负数，这个区间就不是连续的，也证明不需要我们建造哦。

代码实现

  1. import java.util.Scanner;
  2.  
  3. public class 积木大赛
  4. {
  5.     public static void main(String[] args)
  6.     {
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int a[] = new int[100010];
  10.         int b[] = new int[100010];
  11.         for (int i = 1; i <= n; i++)
  12.         {
  13.             a[i] = sc.nextInt();
  14.         }
  15.         for(int i = 1; i <= n; i++)
  16.         {
  17.             b[i] = a[i] - a[i-1];
  18.         }
  19.         int ans = 0;
  20.         for(int i = 1; i <= n; i++)
  21.         {
  22.             if(b[i] > 0) ans += b[i]; //注意：这里要约束b[i]>0
  23.         }
  24.         System.out.println(ans);
  25.     }
  26. }

好了，练习题目就到这里吧，二维差分就不练习了，等小编达到了一定高度再细发...如果本文对你有帮助，就给个一键三连吧，也可以收藏起来观看。

总结

本文一共讲解了一维前缀和，二维前缀和，一维差分，二维差分。主要需要记住使用的公式和分析在什么场景下使用哪一个。需要详细掌握还得多多做题！大家一起加油吧！

 

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号