基础算法篇——前缀和与差分

基础算法篇——前缀和与差分

本次我们介绍基础算法中的前缀和与差分,我们会从下面几个角度来介绍前缀和与差分:

  • 前缀和介绍
  • 一维前缀和
  • 二维前缀和
  • 差分介绍
  • 一维差分
  • 二维差分

前缀和介绍

首先我们来简单介绍一下前缀和:

  • 我们首先定义一个长度为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;     } } 

结束语

好的,关于基础算法篇的前缀和与差分就介绍到这里,希望能为你带来帮助~

发表评论

相关文章