基础算法篇——前缀和与差分
本次我们介绍基础算法中的前缀和与差分,我们会从下面几个角度来介绍前缀和与差分:
- 前缀和介绍
- 一维前缀和
- 二维前缀和
- 差分介绍
- 一维差分
- 二维差分
前缀和介绍
首先我们来简单介绍一下前缀和:
- 我们首先定义一个长度为n的数组,然后我们希望求这个数组的部分长度的总和
如果正常采用我们的for循环来遍历一遍的话:
- 复杂度为O(n)
这时如果我们提前将这些数据保存起来,在多次查询时就会方便很多:
- 我们将数组的第i个值定义为ai
- 我们将数组的前n个值的和定义为Sn
- 其实就是类似于我们数学上的基本算法
我们如果想要求解某一部分的值,只需要用S进行删减即可:
// sum[l,r] = S[r] - S[l-1]
这里我们做一个小小的细节处理:
// 由于我们需要S[r] - S[l-1]完成计算 // 那么当我们的l=0时,我们需要S[r]-S[-1],这明显是不可行的,但是如果我们将整体往前移动一位 // 我们直接让数组从1开始,让S数组也从1开始,并将S[0]=0,这样我们在计算[1,k]之间的数时就可以直接使用S[r]-S[l-1]了
一维前缀和
题型:
- 输入数组长度和一组数组,输入需要查询的前缀和次数,输入需要查询的区块下标,返回对应的sum值
代码展示:
import java.util.Scanner; public class PrefixSum { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 输入数组长度和查询次数 int n = scanner.nextInt(); int k = scanner.nextInt(); // 输入数组内容 int[] arr = new int[n+1]; for (int i = 1; i <= n; i++) { arr[i] = scanner.nextInt(); } // 首先获得Sn int[] sn = new int[n+1]; sn[0] = 0; for (int i = 1; i <= n; i++) { sn[i] = sn[i-1] + arr[i]; } // 开始循环 while (k-- > 0){ // 输入查询值 int l = scanner.nextInt(); int r = scanner.nextInt(); // 查询并输出结果 System.out.println( l + "到" + r +"的数值为:" + (sn[r]-sn[l-1])); } } }
二维前缀和
题型:
- 输入一个n行m列的整数矩阵,再输入k个询问
- 每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2,表示一个子矩阵的左上角坐标和右下角坐标。
- 对于每个询问输出子矩阵中所有数的和。
代码展示:
import java.util.Scanner; public class PrefixSum { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 输入二维数组n,m int n = scanner.nextInt(); int m = scanner.nextInt(); // 输入查询次数 int k = scanner.nextInt(); // 创建数组 int[][] arr = new int[n+1][m+1]; int[][] snn = new int[n+1][m+1]; // 首先给二维数组值 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { arr[i][j] = scanner.nextInt(); } } // Sn基本值 snn[0][0] = 0; snn[0][1] = 0; snn[1][0] = 0; // 给Sn赋值 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { snn[i][j] = snn[i][j-1] + snn[i-1][j] - snn[i-1][j-1] + arr[i][j]; } } // 循环查询 while (k-- > 0){ // 输入遍历位置 int x1 = scanner.nextInt(); int y1 = scanner.nextInt(); int x2 = scanner.nextInt(); int y2 = scanner.nextInt(); // 获得值 int result = snn[x2][y2] - snn[x1][y2] - snn[x2][y1] + snn[x1][y1]; // 开始遍历并返回 System.out.println("从" + x1 + y1 + "到" + x2 + y2 + "的值为:" + result); } } }
差分介绍
我们首先来简单介绍一下差分:
- 差分实际上就是前缀和的相反方法
- 我们首先给出一个数组A,然后构建数组B,使数组A的每个值都对应的数组B的每个值的前缀和
我们给出一个简单的实例:
// 例如我们的题目给出我们一个A数组 int[] A = [1,2,3,4] // 这时我们需要构造一个B数组,使A是B的前缀和,那么B就应该是int[] B = [1,1,1,1] // 实际上我们的B数组赋值十分简单:只需要用a[i]-a[i-1]即可
那么差分又具有什么作用:
// 差分可以用我们新建的数组B来统一管理我们的数组A的一部分内容 // 如果我们想在A的数组上某个区域内都加上c,如果我们直接添加,复杂度为O(n) // 但是如果我们采用B数组添加,那么我们只需要在这个区域的开头+c,在这个区域的末尾-c即可,复杂度为O(1) // 但同时利用这个思想,我们可以对B数组赋值,当我们的开头和结尾都为一个数时 // 就相当于对当前的数b[n]+a[i],对下一个数b[n+1]-a[i],但下一步时我们就会对b[n+1]+a[i+1]正好对应了a[i]-a[i-1]
一维差分
题型:
- 输入一个长度为n的整数序列,接下来输入k个操作。
- 每个操作包含三个整数 l,r,cl,r,c,表示将序列中 [l,r] 之间的每个数加上 cc。
- 请你输出进行完所有操作后的序列
代码展示:
import java.util.Scanner; public class Diff { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 给出n和k int n = scanner.nextInt(); int k = scanner.nextInt(); // 搭建数组 int[] arr = new int[n+1]; int[] brr = new int[n+1]; // 为arr赋值 for (int i = 1; i < n+1; i++) { arr[i] = scanner.nextInt(); } // 为brr赋值 for (int i = 1; i < n+1; i++){ brr[i] = arr[i] - arr[i-1]; } while (k-- > 0){ // 我们为arr的[l,r]区间加上c int l = scanner.nextInt(); int r = scanner.nextInt(); int c = scanner.nextInt(); brr[l] += c; brr[r+1] -= c; } // 然后我们输出结果即可(注意这里输出的需要是由b累计出来的a) for (int i = 1; i < n+1; i++) { brr[i] += brr[i-1]; } // 最后输出结果 for (int i = 1; i < n+1; i++) { System.out.println(brr[i]); } } }
代码修改:
// 但其实我们会发现上述中的b的累加方法实际上和对b的修改方法几乎是一致 // 同样都是b[i]=a[i]-a[i-1],所以我们可以将两个方法合并起来减少代码量 import java.util.Scanner; public class Diff { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 给出n和k int n = scanner.nextInt(); int k = scanner.nextInt(); // 搭建数组 int[] arr = new int[n+1]; int[] brr = new int[n+1]; // 为arr赋值 for (int i = 1; i < n+1; i++) { arr[i] = scanner.nextInt(); } // 为brr赋值 for (int i = 1; i < n+1; i++){ insert(i,i,arr[i]); } while (k-- > 0){ // 我们为arr的[l,r]区间加上c int l = scanner.nextInt(); int r = scanner.nextInt(); int c = scanner.nextInt(); insert(l,r,c); } // 然后我们输出结果即可(注意这里输出的需要是由b累计出来的a) for (int i = 1; i < n+1; i++) { brr[i] += brr[i-1]; } // 最后输出结果 for (int i = 1; i < n+1; i++) { System.out.println(brr[i]); } } // 合并为一个方法 public void inset(int l,int r,int c){ b[l]+=c; b[r+1]+=c; } }
二维差分
题型:
- 先输入一个n行m列的数组,输入一个k作为增加区块次数
- 每次增加区块需要输入x1,y1,x2,y2,c作为区块左上角和区块右下角以及该区块增加的数
- 最后我们输出打印整个数组
代码展示:
import java.util.Scanner; public class Diff { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 获得m,n,k int m = scanner.nextInt(); int n = scanner.nextInt(); int k = scanner.nextInt(); // 输入数组A int[][] arr = new int[m+2][n+2]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { arr[i][j] = scanner.nextInt(); } } // 我们同样采用insert方法封装一个方法来是同步实现brr的数据赋值以及brr的部分区间赋值 int[][] brr = new int[m+2][n+2]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { insert(i,j,i,j,arr[i][j],brr); } } // 进行差分 while (k-- > 0){ int x1 = scanner.nextInt(); int y1 = scanner.nextInt(); int x2 = scanner.nextInt(); int y2 = scanner.nextInt(); int c = scanner.nextInt(); insert(x1,y1,x2,y2,c,brr); } // 我们获得brr总和为arr的值 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { brr[i][j] += brr[i][j-1] + brr[i-1][j] - brr[i-1][j-1]; } } // 我们输出打印 for (int i = 1;i <= m;i++){ for (int j = 1; j <= n; j++) { System.out.print(brr[i][j] + " "); } System.out.println(); } } public static void insert(int x1,int y1,int x2,int y2,int c,int[][] brr){ brr[x1][y1] += c; brr[x1][y2+1] -= c; brr[x2+1][y1] -= c; brr[x2+1][y2+1] += c; } }
结束语
好的,关于基础算法篇的前缀和与差分就介绍到这里,希望能为你带来帮助~