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

时间：2022-11-07 11:30:38

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

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

前缀和介绍

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

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

结束语

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

相关文章