基礎演演算法篇——字首和與差分

本次我們介紹基礎演演算法中的字首和與差分，我們會從下面幾個角度來介紹字首和與差分：

• 字首和介紹
• 一維字首和
• 二維字首和
• 差分介紹
• 一維差分
• 二維差分

字首和介紹

首先我們來簡單介紹一下字首和：

• 我們首先定義一個長度為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;
    }
}

結束語

好的，關於基礎演演算法篇的字首和與差分就介紹到這裡，希望能為你帶來幫助~