本系列文章將于2021年整理出版，前驅教材：《演算法競賽入門到進階》 清華大學出版社
網購：京東 當當 ??作者簽名書：點我
有建議請加QQ 群：567554289

?? 差分是一種處理資料的巧妙而簡單的方法，它應用于區間的修改和詢問問題，把給定的資料元素集A分成很多區間，對這些區間做很多次操作，每次操作是對某個區間內的所有元素做相同的加減操作，若一個個地修改這個區間內的每個元素，非常耗時，引入“差分陣列”D，當修改某個區間時，只需要修改這個區間的“端點”，就能記錄整個區間的修改，而對端點的修改非常容易，是 O ( 1 ) O(1) O(1)復雜度的，當所有的修改操作結束后，再利用差分陣列，計算出新的A，
??資料A可以是一維的線性陣列 a [ ] a[] a[]、二維矩陣 a [ ] [ ] a[][] a[][]、三維立體 a [ ] [ ] [ ] a[][][] a[][][]，相應地，定義差分陣列 D [ ] 、 D [ ] [ ] 、 D [ ] [ ] [ ] D[]、D[][]、D[][][] D[]、D[][]、D[][][]，一維差分很容易理解，二維和三維需要一點想象力，

1. 一維差分

1.1 一維差分的概念

?? 討論這樣一個場景：
?? （1）給定一個長度為n的一維陣列 a [ ] a[] a[]，陣列內每個元素有初始值，
?? （2）修改操作：做m次區間修改，每次修改對區間內所有元素做相同的加減操作，例如第 i i i次修改，把區間 [ L i , R i ] [Li, Ri] [Li,Ri]內所有元素加上 d i di di，
?? （3）詢問操作：詢問一個元素的新值是多少，
?? 如果簡單地用暴力法編碼，那么每次修改的復雜度是 O ( n ) O(n) O(n)的，m次修改共 O ( m n ) O(mn) O(mn)，總復雜度 O ( m n ) O(mn) O(mn)，效率很差，利用差分法，可以把復雜度減少到 O ( m + n ) O(m+n) O(m+n)，
?? 在差分法中，用到了兩個陣列：原陣列 a [ ] a[] a[]、差分陣列 D [ ] D[] D[]，
?? 差分陣列D[]的定義是 D [ k ] = a [ k ] ? a [ k ? 1 ] D[k] = a[k] - a[k-1] D[k]=a[k]?a[k?1]，即原陣列 a [ ] a[] a[]的相鄰元素的差，從定義可以推出 a [ k ] = D [ 1 ] + D [ 2 ] + . . . + D [ k ] a[k] = D[1] + D[2] + ... + D[k] a[k]=D[1]+D[2]+...+D[k] ，也就是說， a [ ] a[] a[]是 D [ ] D[] D[]的前綴和，這個公式揭示了 a [ ] a[] a[]和 D [ ] D[] D[]的關系，“差分是前綴和的逆運算”，它把求 a [ k ] a[k] a[k]轉化為求D的前綴和，為加深對前綴和的理解，可以把每個 D [ ] D[] D[]看成一條直線上的小線段，它的兩端是相鄰的 a [ ] a[] a[]；這些小線段相加，就得到了從起點開始的長線段 a [ ] a[] a[]，
?? 注意， a [ ] a[] a[]和 D [ ] D[] D[]的值都可能為負，下面圖中所有的 D [ ] D[] D[]都是長度為正的線段，只是為了方便圖示，

??
??如何用差分陣列記錄區間修改？為什么利用差分陣列能提升修改的效率呢？
??把區間 [ L , R ] [L, R] [L,R]內每個元素加上 d d d，對應的 D [ ] D[] D[]做以下操作：
??（1）把 D [ L ] D[L] D[L]加上 d d d：

     D[L] += d

??（2）把 D [ R + 1 ] D[R+1] D[R+1]減去 d d d：

     D[R+1] -= d

??每次操作只需要修改區間 [ L , R ] [L, R] [L,R]的兩個端點的 D [ ] D[] D[]值，復雜度是 O ( 1 ) O(1) O(1)的，經過這種操作后，原來直接在 a [ ] a[] a[]上做的復雜度為 O ( n ) O(n) O(n)的區間修改操作，就變成了在 D [ ] D[] D[]上做的復雜度為 O ( 1 ) O(1) O(1)的端點操作，
??利用 D [ ] D[] D[]，能精確地實作只修改區間內元素的目的，而不會修改區間外的 a [ ] a[] a[]值，因為前綴和 a [ x ] = D [ 1 ] + D [ 2 ] + . . . + D [ x ] a[x] = D[1] + D[2] + ... + D[x] a[x]=D[1]+D[2]+...+D[x]，有：
??（1） 1 ≤ x < L 1 ≤ x < L 1≤x<L，前綴和 a [ x ] a[x] a[x]不變；
??（2） L ≤ x ≤ R L ≤ x ≤ R L≤x≤R，前綴和 a [ x ] a[x] a[x]增加了 d d d；
??（3） R < x ≤ N R < x ≤ N R<x≤N，前綴和 a [ x ] a[x] a[x]不變，因為被 D [ R + 1 ] D[R+1] D[R+1]中減去的 d d d抵消了，
??完成區間修改并得到 D [ ] D[] D[]后，最后用 D [ ] D[] D[]計算 a [ ] a[] a[]，復雜度是 O ( n ) O(n) O(n)的，m次區間修改和1次查詢，總復雜度為 O ( m + n ) O(m + n) O(m+n)，比暴力法的 O ( m n ) O(mn) O(mn)好多了，
??下面給出一個例題，

Color the ball hdu 1556 http://acm.hdu.edu.cn/showproblem.php?pid=1556
問題描述：N個氣球排成一排，從左到右依次編號為1, 2, 3 … N，每次給定2個整數L, R(L<= R)，lele從氣球L開始到氣球R依次給每個氣球涂一次顏色，但是N次以后lele已經忘記了第I個氣球已經涂過幾次顏色了，你能幫他算出每個氣球被涂過幾次顏色嗎？
輸入：每個測驗實體第一行為一個整數N，(N <= 100000)，接下來的N行，每行包括2個整數L, R(1 <= L<= R<= N)，當N = 0，輸入結束，
輸出：每個測驗實體輸出一行，包括N個整數，第I個數代表第I個氣球總共被涂色的次數，

??這個例題是簡單差分法的直接應用，下面給出代碼，代碼第13、14行是區間修改，第17行的 a [ i ] = a [ i ? 1 ] + D [ i ] a[i] = a[i-1] + D[i] a[i]=a[i?1]+D[i]，即利用 D [ ] D[] D[]求得了最后的 a [ ] a[] a[]，這個式子就是 a [ i ] ? a [ i ? 1 ] = D [ i ] a[i] - a[i-1] = D[i] a[i]?a[i?1]=D[i]，它是差分陣列的定義，
??注意 a [ ] a[] a[]的計算方法， a [ i ] = a [ i ? 1 ] + D [ i ] a[i] = a[i-1] + D[i] a[i]=a[i?1]+D[i]是一個遞推公式，通過它能在一個 i i i回圈中求得所有的 a [ ] a[] a[]，如果不用遞推，而是直接用前綴和 a [ k ] = D [ 1 ] + D [ 2 ] + . . . + D [ k ] a[k]=D[1] + D[2] + ... + D[k] a[k]=D[1]+D[2]+...+D[k] 來求所有的 a [ ] a[] a[]，就需要用兩個回圈 i 、 k i、k i、k，

//hdu 1556用差分陣列求解
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 100010;
int a[Maxn],D[Maxn];               //a是氣球，D是差分陣列

int main(){
    int n;
    while(~scanf("%d",&n)) { 
        memset(a,0,sizeof(a)); memset(D,0,sizeof(D));
        for(int i=1;i<=n;i++){
            int L,R; scanf("%d%d",&L,&R);
            D[L]++;                 //區間修改，這里d=1
            D[R+1]--;
        }
//小技巧：17行到20行，把a[]改成D[]也行
        for(int i=1;i<=n;i++){              //求原陣列
            a[i] = a[i-1] + D[i];           //差分，求前綴和a[]，a[i]就是氣球i的值
            if(i!=n)  printf("%d ", a[i]);  //逐個列印結果
            else      printf("%d\n",a[i]);
        }        
    }
    return 0;
}

??上面的代碼用了一個小技巧，可以省掉 a [ ] a[] a[]，從而節省空間，在17行后求原陣列 a [ ] a[] a[]的時候，在推導式子 a [ i ] = a [ i ? 1 ] + D [ i ] a[i] = a[i-1] + D[i] a[i]=a[i?1]+D[i]時，把已經使用過的較小的 D [ ] D[] D[]直接當成 a [ ] a [] a[]即可，把第17~20行的 a [ ] 改 為 D [ ] a[]改為D[] a[]改為D[]，也能通過，這個技巧在后面的二維差分、三維差分中也能用，節省一倍的空間，

1.2 差分的局限性

??讀者已經注意到，利用差分陣列 D [ ] D[] D[]可以把 O ( n ) O(n) O(n)的區間修改，變成 O ( 1 ) O(1) O(1)的端點修改，從而提高了修改操作的效率，
??但是，一次查詢操作，即查詢某個 a [ i ] a[i] a[i]，需要用 D [ ] D[] D[]計算整個原陣列 a [ ] a[] a[]，計算量是 O ( n ) O(n) O(n)的，即一次查詢的復雜度是 O ( n ) O(n) O(n)的，在上面的例題中，如果查詢不是發生了一次，而是這樣：有m次修改，有k次查詢，且修改和查詢的順序是隨機的，此時總復雜度是：m次修改復雜度 O ( m ) O(m) O(m)，k次查詢復雜度 O ( k n ) O(kn) O(kn)，總復雜度 O ( m + k n ) O(m + kn) O(m+kn)，還不如直接用暴力法，總復雜度 O ( m n + k ) O(mn + k) O(mn+k)，
??這種題型是“區間修改+單點查詢”，用差分陣列往往不夠用，因為差分陣列對“區間修改”很高效，但是對“單點查詢”并不高效，此時需要用樹狀陣列和線段樹來求解，詳情見第4章的樹狀陣列、線段樹專題，在樹狀陣列專題中，重新講解了hdu 1556這道例題，
??樹狀陣列常常結合差分陣列來解決更復雜的問題，見本博客的樹狀陣列專題，差分陣列也常用于“樹上差分”，見本博客LCA專題的“樹上差分”，

2. 二維差分

??從一維差分容易擴展到二維差分，一維是線性陣列，一個區間 [ L , R ] [L, R] [L,R]有兩個端點；二維是矩陣，一個區間由四個端點圍成，
??下面給出一個模板題，

地毯 洛谷P3397 https://www.luogu.com.cn/problem/P3397
問題描述：在 n×n 的格子上有m個地毯，給出這些地毯的資訊，問每個點被多少個地毯覆寫，
輸入： 第一行是兩個正整數n，m，接下來m行，每行2個坐標(x1, y1)和(x2, y2)，代表一塊地毯，左上角是(x1, y1)，右下角是(x2, y2)，
輸出： 輸出n行，每行n個正整數，第i行第j列的正整數表示(i, j)這個格式被多少地毯覆寫，

??這一題是hdu 1556的二維擴展，其修改操作和查詢操作完全一樣，
??存盤矩陣需要很大的空間，如果題目有空間限制，例如100M，那么二維差分能處理多大的n？定義兩個二維矩陣 a [ ] [ ] 和 D [ ] [ ] a[][]和D[][] a[][]和D[][]，設矩陣的每個元素是2位元組的 i n t int int型，可以計算出最大的n = 5000，不過，也可以不定義 a [ ] [ ] a[][] a[][]，而是像一維情況下一樣，直接用 D [ ] [ ] 來 表 示 a [ ] [ ] D[][]來表示a[][] D[][]來表示a[][]，這樣能剩下一半的空間，
??在用差分之前，先考慮能不能用暴力法，每次修改復雜度是 O ( n 2 ) O(n^2) O(n2)，共m次，總復雜度 O ( m × n 2 ) O(m×n^2) O(m×n2)，超時，
??二維差分的復雜度是多少？一維差分的一次修改是 O ( 1 ) O(1) O(1)的，二維差分的修改估計也是 O ( 1 ) O(1) O(1)的；一維差分的一次查詢是 O ( n ) O(n) O(n)的，二維差分是 O ( n 2 ) O(n^2) O(n2)的，所以二維差分的總復雜度是 O ( m + n 2 ) O(m + n^2) O(m+n2)，由于計算一次二維矩陣的值需要 O ( n 2 ) O(n^2) O(n2)次計算，所以二維差分已經達到了最好的復雜度，
??下面從一維差分推廣到二維差分，
??（1）前綴和，
??在一維差分中，原陣列 a [ ] a[] a[]是從第1個 D [ 1 ] D[1] D[1]開始的差分陣列 D [ ] D[] D[]的前綴和： a [ k ] = D [ 1 ] + D [ 2 ] + . . . + D [ k ] a[k] = D[1] + D[2] + ... + D[k] a[k]=D[1]+D[2]+...+D[k]，
??在二維差分中， a [ ] [ ] a[][] a[][]是差分陣列 D [ ] [ ] D[][] D[][]的前綴和，即由原點坐標 ( 1 , 1 ) (1, 1) (1,1)和坐標 ( i , j ) (i, j) (i,j)圍成的矩陣中，所有的 D [ ] [ ] D[][] D[][]相加等于 a [ i ] [ j ] a[i][j] a[i][j]，為加深對前綴和的理解，可以把每個 D [ ] [ ] D[][] D[][]看成一個小格；在坐標 ( 1 , 1 ) 和 ( i , j ) (1, 1)和(i, j) (1,1)和(i,j)所圍成的范圍內，所有小格子加起來的總面積，等于 a [ i ] [ j ] a[i][j] a[i][j]，下面的圖中，每個格子的面積是一個 D [ ] [ ] D[][] D[][]，例如陰影格子是 D [ i ] [ j ] D[i][j] D[i][j]，它由4個坐標點定義： ( i ? 1 , j ) 、 ( i , j ) 、 ( i ? 1 , j ? 1 ) 、 ( i , j ? 1 ) (i-1, j)、(i, j)、(i-1, j-1)、(i, j-1) (i?1,j)、(i,j)、(i?1,j?1)、(i,j?1)，坐標點 ( i , j ) (i, j) (i,j)的值是 a [ i ] [ j ] a[i][j] a[i][j]，它等于坐標 ( 1 , 1 ) 和 ( i , j ) (1, 1)和(i, j) (1,1)和(i,j)所圍成的所有格子的總面積，圖中故意把小格子畫得長寬不同，是為了體現它們的面積不同，

??
??注意在一些題目中， D [ ] [ ] D[][] D[][]可以為負，圖中把 D [ ] [ ] D[][] D[][]用“面積”來演示，而面積都是正的，這個圖示只是為了加深對前綴和的理解，
??（2）差分的定義，在一維情況下， D [ i ] = a [ i ] ? a [ i ? 1 ] D[i] = a[i] - a[i-1] D[i]=a[i]?a[i?1]，在二維情況下，差分變成了相鄰的 a [ ] [ ] a[][] a[][]的“面積差”，計算公式是： D [ i ] [ j ] = a [ i ] [ j ] – a [ i ? 1 ] [ j ] – a [ i ] [ j ? 1 ] + a [ i ? 1 ] [ j ? 1 ] D[i][j] = a[i][j] – a[i-1][j] – a[i][j-1] + a[i-1][j-1] D[i][j]=a[i][j]–a[i?1][j]–a[i][j?1]+a[i?1][j?1]，這個公式可以通過上面的圖來觀察，陰影方格表示 D [ i ] [ j ] D[i][j] D[i][j]的值，它的面積這樣求：大面積 a [ i ] [ j ] a[i][j] a[i][j]減去兩個小面積 a [ i ? 1 ] [ j ] 、 a [ i ] [ j ? 1 ] a[i-1][j]、a[i][j-1] a[i?1][j]、a[i][j?1]，由于兩個小面積的公共面積 a [ i ? 1 ] [ j ? 1 ] a[i-1][j-1] a[i?1][j?1]被減了2次，所以需要加回來1次，
??（3）區間修改，在一維情況下，做區間修改只需要修改區間的兩個端點的 D [ ] D[] D[]值，在二維情況下，一個區間是一個小矩陣，有4個端點，只需要修改這4個端點的 D [ ] [ ] D[][] D[][]值，例如坐標點 ( x 1 , y 1 ) (x1, y1) (x1,y1) ~ ( x 2 , y 2 ) (x2, y2) (x2,y2)定義的區間，對應4個端點的 D [ ] [ ] D[][] D[][]：

D[x1][y1]     += d;     //二維區間的起點
D[x1][y2+1]   -= d;     //把x看成常數，y從y1到y2+1
D[x2+1][y1]   -= d;     //把y看成常數，x從x1到x2+1
D[x2+1][y2+1] += d;     //由于前兩式把d減了2次，多減了1次，這里加1次回來

??下圖是區間修改的圖示，2個黑色點圍成的矩形是題目給出的區間修改范圍，只需要改變4個 D [ ] [ ] D[][] D[][]值，即改變圖中的4個陰影塊的面積，讀者可以用這個圖，觀察每個坐標點的 a [ ] [ ] a[][] a[][]值的變化情況，例如符號“?”標記的坐標 ( x 2 + 1 , y 2 ) (x2+1, y2) (x2+1,y2)，它在修改的區間之外； a [ x 2 + 1 ] [ y 2 ] a[x2+1][y2] a[x2+1][y2]的值是從 ( 1 , 1 ) 到 ( x 2 + 1 , y 2 ) (1,1)到(x2+1, y2) (1,1)到(x2+1,y2)的總面積，在這個范圍內， D [ x 1 ] [ y 1 ] + d ， D [ x 2 + 1 ] [ y 1 ] ? d D[x1][y1]+d，D[x2+1][y1]-d D[x1][y1]+d，D[x2+1][y1]?d，兩個 d d d抵消， a [ x 2 + 1 ] [ y 2 ] a[x2+1][y2] a[x2+1][y2]保持不變，

??下面給出洛谷P3397的兩種實作，

2.1 用差分陣列的遞推公式求前綴和

??前綴和 a [ ] [ ] a[][] a[][]的計算用到了遞推公式：
???? a [ i ] [ j ] = D [ i ] [ j ] + a [ i ? 1 ] [ j ] + a [ i ] [ j ? 1 ] ? a [ i ? 1 ] [ j ? 1 ] ; a[i][j] = D[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]; a[i][j]=D[i][j]+a[i?1][j]+a[i][j?1]?a[i?1][j?1];
??16行到23行用 D [ ] [ ] D[][] D[][]推出 a [ ] [ ] a[][] a[][]并列印出來，
??為了節約空間，可以不定義 a [ ] [ ] a[][] a[][]，而是把用過的 D [ ] [ ] D[][] D[][]看成 a [ ] [ ] a[][] a[][]，這個小技巧在一維差分中介紹過，

#include<bits/stdc++.h>
using namespace std;
int D[5000][5000];     //差分陣列
//int a[5000][5000];   //原陣列，不定義也行
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        D[x1][y1]     += 1;        //計算差分陣列
        D[x2+1][y1]   -= 1;
        D[x1][y2+1]   -= 1;
        D[x2+1][y2+1] += 1;
    }
    for(int i=1;i<=n;++i){   //根據差分陣列計算原矩陣的值（想象成求小格子的面積和）
        for(int j=1;j<=n;++j){      //把用過的D[][]看成a[][]，就不用再定義a[][]了
            //a[i][j] = D[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
            //printf("%d ",a[i][j]);  //這兩行和下面兩行的效果一樣
            D[i][j] += D[i-1][j]+D[i][j-1]-D[i-1][j-1];
            printf("%d ",D[i][j]);
        }
        printf("\n");//換行
    }
    return 0;
}

2.2 直接計算前綴和

??其實不用遞推公式，而是直接求前綴和也行，根據圖2，前綴和是總面積，分別從 x x x方向和 y y y方向，用兩次回圈計算，并直接用 D [ ] [ ] D[][] D[][]記錄結果，最后算出的 D [ ] [ ] D[][] D[][]就是 a [ ] [ ] a[][] a[][]，

??以陰影處的 D [ 2 ] [ 2 ] D[2][2] D[2][2]為例，它最后的值代表 a [ 2 ] [ 2 ] a[2][2] a[2][2]，是4個小格子的總面積：
???? D [ 1 ] [ 1 ] + D [ 1 ] [ 2 ] + D [ 2 ] [ 1 ] + D [ 2 ] [ 2 ] D[1][1] + D[1][2] + D[2][1] + D[2][2] D[1][1]+D[1][2]+D[2][1]+D[2][2]
??計算程序是：
??（1）先累加計算 y y y方向，得：
???? D [ 1 ] [ 2 ] = D [ 1 ] [ 1 ] + D [ 1 ] [ 2 ] 、 D [ 2 ] [ 2 ] = D [ 2 ] [ 1 ] + D [ 2 ] [ 2 ] D[1][2] = D[1][1]+ D[1][2]、D[2][2] = D[2][1]+ D[2][2] D[1][2]=D[1][1]+D[1][2]、D[2][2]=D[2][1]+D[2][2]
??（2）再累加計算 x x x方向，得：
???? D [ 2 ] [ 1 ] = D [ 1 ] [ 1 ] + D [ 2 ] [ 1 ] 、 D [ 2 ] [ 2 ] = D [ 1 ] [ 2 ] + D [ 2 ] [ 2 ] = D [ 1 ] [ 1 ] + D [ 1 ] [ 2 ] + D [ 2 ] [ 1 ] + D [ 2 ] [ 2 ] D[2][1]=D[1][1]+D[2][1]、D[2][2]=D[1][2]+D[2][2]= D[1][1]+D[1][2]+ D[2][1]+ D[2][2] D[2][1]=D[1][1]+D[2][1]、D[2][2]=D[1][2]+D[2][2]=D[1][1]+D[1][2]+D[2][1]+D[2][2]
??實際上，在這個計算程序中， D [ 1 ] [ 1 ] 、 D [ 1 ] [ 2 ] 、 D [ 2 ] [ 1 ] 、 D [ 2 ] [ 2 ] D[1][1]、D[1][2]、D[2][1]、D[2][2] D[1][1]、D[1][2]、D[2][1]、D[2][2]都更新了，計算結果代表了 a [ 1 ] [ 1 ] 、 a [ 1 ] [ 2 ] 、 a [ 2 ] [ 1 ] 、 a [ 2 ] [ 2 ] a[1][1]、a[1][2]、a[2][1]、a[2][2] a[1][1]、a[1][2]、a[2][1]、a[2][2]，
??把方法1代碼的16-24行替換為下面的代碼，最后得到的 D [ ] [ ] D[][] D[][]就是所有的前綴和，即最新的 a [ ] [ ] a[][] a[][]，請對照圖2理解代碼，

    for(int i=1; i<=n; ++i)           
        for(int j=1; j<n; ++j)        //注意這里是j<n
            D[i][j+1] += D[i][j];     //把i看成定值，先累加計算j方向
    for(int j=1; j<=n; ++j)
        for(int i=1; i<n; ++i)        //注意這里是i<n
            D[i+1][j] += D[i][j];     //把j看成定值，再累加計算i方向
    for(int i=1; i<=n; ++i) {         //列印
        for(int j=1; j<=n; ++j)
             printf("%d ",D[i][j]);
        printf("\n");                 //換行
    }

??對比這兩種代碼：
??（1）這兩種代碼的復雜度是一樣的，從計算量上看，沒有優劣之分，
??（2）代碼2不如代碼1清晰簡潔，所以代碼2這種寫法一般也用不著，
??（3）代碼2也有優點，它不需要用到遞推公式，而是直接求前綴和，
??這里給出代碼2這種方法，是為了在下一小節的三維差分中使用它，由于在三維情況下，差分陣列的 D [ ] [ ] [ ] D[][][] D[][][]和原陣列 a [ ] [ ] [ ] a[][][] a[][][]的遞推公式很難寫出來，所以用代碼2這種方法更容易編碼，

3. 三維差分

??三維差分的模板代碼比較少見，
??三維差分比較復雜，請結合本節中的幾何圖進行理解，
??與一維差分、二維差分的思路類似，下面給出三維差分的有關特性，
??（1）元素的值用三維陣列 a [ ] [ ] [ ] a[][][] a[][][]來定義，差分陣列 D [ ] [ ] [ ] D[][][] D[][][]也是三維的，把三維差分想象成在立體空間上的操作，一維的區間是一個線段，二維是矩形，那么三維就是立體塊，一個小立體塊有8個頂點，所以三維的區間修改，需要修改8個 D [ ] [ ] [ ] D[][][] D[][][]值，
??（2）前綴和，
??在二維差分中， a [ ] [ ] a[][] a[][]是差分陣列 D [ ] [ ] D[][] D[][]的前綴和，即由原點坐標 ( 1 , 1 ) (1, 1) (1,1)和坐標 ( i , j ) (i, j) (i,j)圍成的矩陣中，所有的 D [ ] [ ] D[][] D[][]（看成小格子）相加等于 a [ i ] [ j ] a[i][j] a[i][j]（看成總面積），
??在三維差分中， a [ ] [ ] [ ] a[][][] a[][][]是差分陣列 D [ ] [ ] [ ] D[][][] D[][][]的前綴和，即由原點坐標 ( 1 , 1 , 1 ) (1, 1, 1) (1,1,1)和坐標 ( i , j , k ) (i, j, k) (i,j,k)所標記的范圍中，所有的 D [ ] [ ] [ ] D[][][] D[][][]相加等于 a [ i ] [ j ] [ k ] a[i][j][k] a[i][j][k]，把每個 D [ ] [ ] [ ] D[][][] D[][][]看成一個小立方體；在坐標 ( 1 , 1 , 1 ) (1, 1, 1) (1,1,1)和 ( i , j , k ) (i, j, k) (i,j,k)所圍成的空間中，所有小立體塊加起來的總體積，等于 a [ i ] [ j ] [ k ] a[i][j][k] a[i][j][k]，每個小立方體由8個坐標點定義，見下面圖中的坐標點，坐標點 ( i , j , k ) (i, j, k) (i,j,k)的值是 a [ i ] [ j ] [ k ] a[i][j][k] a[i][j][k]； D [ i ] [ j ] [ k ] D[i][j][k] D[i][j][k]的值是圖中小立方體的體積，

??（3）差分的定義，在三維情況下，差分變成了相鄰的 a [ ] [ ] [ ] a[][][] a[][][]的“體積差”，如何寫出差分的遞推計算公式？
??一維差分和二維差分的遞推計算公式很好寫，
??三維差分， D [ i ] [ j ] [ k ] D[i][j][k] D[i][j][k]的幾何意義是圖中小立方體的體積，它可以通過這個小立方體的8個頂點的值推出來，思路與二維情況下類似，二維的 D [ ] [ ] D[][] D[][]是通過小矩形的四個頂點的 a [ ] [ ] a[][] a[][]值來計算的，不過，三維情況下，遞推計算公式很難寫，8個頂點有8個 a [ ] [ ] [ ] a[][][] a[][][]，把腦袋繞暈了也不容易寫對，
上一小節的二維差分中，曾用過另一種方法，直接對D陣列求前綴和，在三維情況下也可以用這種方法求前綴和，得到所有的 a [ ] [ ] [ ] a[][][] a[][][]的最新值，
??（4）區間修改，在三維情況下，一個區間是一個立方體，有8個頂點，只需要修改這8個頂點的 D [ ] [ ] [ ] D[][][] D[][][]值，例如坐標點 ( x 1 , y 1 , z 1 ) (x1, y1, z1) (x1,y1,z1) ~ ( x 2 , y 2 , z 2 ) (x2, y2, z2) (x2,y2,z2)定義的區間，對應8個 D [ ] [ ] [ ] D[][][] D[][][]，請對照上面的圖來想象它們的位置，

D[x1][y1][z1]       += d;   //前面：左下頂點，即區間的起始點
D[x2+1][y1][z1]     -= d;   //前面：右下頂點的右邊一個點
D[x1][y1][z2+1]     -= d;   //前面：左上頂點的上面一個點
D[x2+1][y1][z2+1]   += d;   //前面：右上頂點的斜右上方一個點
D[x1][y2+1][z1]     -= d;   //后面：左下頂點的后面一個點
D[x2+1][y2+1][z1]   += d;   //后面：右下頂點的斜右后方一個點
D[x1][y2+1][z2+1]   += d;   //后面：左上頂點的斜后上方一個點
D[x2+1][y2+1][z2+1] -= d;   //后面：右上頂點的斜右上后方一個點，即區間終點的后一個點

下面給出一個三維差分的例題，

三體攻擊 藍橋杯2018年省賽A組
提交地址：https://www.lanqiao.cn/problems/180/learning/
問題描述：三體人將對地球發起攻擊，為了抵御攻擊，地球人派出了n = A × B × C 艘戰艦，在太空中排成一個 A 層 B 行 C 列的立方體，其中，第 i 層第 j 行第 k 列的戰艦（記為戰艦 (i,?j,?k)）的生命值為 s(i,?j,?k)，
三體人將會對地球發起 m 輪“立方體攻擊”，每次攻擊會對一個小立方體中的所有戰艦都造成相同的傷害，具體地，第 t 輪攻擊用 7 個引數 x1, x2,?y1,?y2,?z1,?z2,?d 描述；
所有滿足i∈[x1,?x2], j∈[y1,?y2], k∈[z1,?z2] 的戰艦 (i,?j,?k) 會受到 d 的傷害，如果一個戰艦累計受到的總傷害超過其防御力，那么這個戰艦會爆炸，
地球指揮官希望你能告訴他，第一艘爆炸的戰艦是在哪一輪攻擊后爆炸的，
輸入：第一行包括 4 個正整數 A,?B,?C,?m；
第二行包含 A × B × C 個整數，其中第 ((i ? 1)×B + (j ? 1)) × C + (k ? 1)+1 個數為 s(i,?j,?k)；
第 3 到第 m + 2 行中，第 (t ? 2) 行包含 7 個正整數 x1, x2,?y1,?y2,?z1,?z2,?d，
A × B × C?≤?10^6,?m?≤?10^6,?0?≤?s(i,?j,?k),?d?≤?10^9，
輸出：輸出第一個爆炸的戰艦是在哪一輪攻擊后爆炸的，保證一定存在這樣的戰艦，

??首先看資料規模，有 n = 1 0 6 n=10^6 n=106個點， m = 1 0 6 m=10^6 m=106次攻擊，如果用暴力法，統計每次攻擊后每個點的生命值，那么復雜度是 O ( m n ) O(mn) O(mn)的，超時，
??本題適合用三維差分，每次攻擊只修改差分陣列 D [ ] [ ] [ ] D[][][] D[][][]，一次修改的復雜度是 O ( 1 ) O(1) O(1)， m m m次修改的總復雜度只有 O ( m ) O(m) O(m)，
??但是光用差分陣列并不能解決問題，因為在差分陣列上查詢區間內的每個元素是否小于0，需要用差分陣列來計算區間內每個元素的值，復雜度是 O ( n ) O(n) O(n)的，合起來的總復雜度還是O(mn)的，跟暴力法的復雜度一樣，
??本題需要結合第二個演算法：二分法，從第1次修改到第m次修改，肯定有一次修改是臨界點，在臨界點前，沒有負值（戰艦爆炸）；在臨界點后，出現了負值，且后面一直有負值，那么對m進行二分，就能在 O ( l o g m ) O(logm) O(logm)次內找到這個臨界點，這就是答案，總復雜度 O ( n l o g m ) O(nlogm) O(nlogm)，
下面給出代碼，其中check()函式包含了三維差分的全部內容，代碼有幾個關鍵點：
??（1）沒有定義 a [ ] [ ] [ ] a[][][] a[][][]，而是用 D [ ] [ ] [ ] D[][][] D[][][]來代替，
??（2）壓維，直接定義三維差分陣列 D [ ] [ ] [ ] D[][][] D[][][]不太方便，雖然坐標點總數量 n = A × B × C = 1 0 6 n = A × B × C = 10^6 n=A×B×C=106比較小，但是每一維都需要定義到 1 0 6 10^6 106，那么總空間就是 1 0 1 8 10^18 1018，經過壓維，用一維陣列 D [ ] D[] D[]，總長度仍然是 1 0 6 10^6 106的，這個技巧很有用，
??（3）check()中19-26行，在 D [ ] D[] D[]上記錄區間修改，
??（4）check()中29-40行的3個for回圈計算前綴和，原理見二維差分的代碼2，它分別從 x 、 y 、 z x、y、z x、y、z三個方向累加小立方體的體積，計算出所有的前綴和，

#include<stdio.h>

int A,B,C,n,m;
const int Maxn = 1000005;
int s[Maxn];   //存盤艦隊生命值
int D[Maxn];   //三維差分陣列（壓維）；同時也用來計算每個點的攻擊值
int x2[Maxn], y2[Maxn], z2[Maxn]; //存盤區間修改的范圍，即攻擊的范圍
int x1[Maxn], y1[Maxn], z1[Maxn]; 

int d[Maxn];                    //記錄傷害，就是區間修改
int num(int x,int y,int z) {  
//小技巧：壓維，把三維坐標[(x,y,z)轉為一維的((x-1)*B+(y-1))*C+(z-1)+1
    if (x>A || y>B || z>C) return 0;
    return ((x-1)*B+(y-1))*C+(z-1)+1;
}
bool check(int x){              //做x次區間修改，即檢查經過x次攻擊后是否有戰艦爆炸
    for (int i=1; i<=n; i++)  D[i]=0;  //差分陣列的初值，本題是0
    for (int i=1; i<=x; i++) {         //用三維差分陣列記錄區間修改：有8個區間端點
        D[num(x1[i],  y1[i],  z1[i])]   += d[i];
        D[num(x2[i]+1,y1[i],  z1[i])]   -= d[i];
        D[num(x1[i],  y1[i],  z2[i]+1)] -= d[i];
        D[num(x2[i]+1,y1[i],  z2[i]+1)] += d[i];
        D[num(x1[i],  y2[i]+1,z1[i])]   -= d[i];
        D[num(x2[i]+1,y2[i]+1,z1[i])]   += d[i];
        D[num(x1[i],  y2[i]+1,z2[i]+1)] += d[i];
        D[num(x2[i]+1,y2[i]+1,z2[i]+1)] -= d[i];
    }
    //下面從x、y、z三個方向計算前綴和
    for (int i=1; i<=A; i++)
        for (int j=1; j<=B; j++)
            for (int k=1; k<C; k++)        //把x、y看成定值，累加z方向
                D[num(i,j,k+1)] += D[num(i,j,k)];
    for (int i=1; i<=A; i++)
        for (int k=1; k<=C; k++)
            for (int j=1; j<B; j++)        //把x、z看成定值，累加y方向
                D[num(i,j+1,k)] += D[num(i,j,k)];
    for (int j=1; j<=B; j++)
        for (int k=1; k<=C; k++)
            for (int i=1; i<A; i++)        //把y、z看成定值，累加x方向
                D[num(i+1,j,k)] += D[num(i,j,k)];
    for (int i=1; i<=n; i++)    //最后判斷是否攻擊值大于生命值
        if (D[i]>s[i])
            return true;
    return false;
}
int main() {
    scanf("%d%d%d%d", &A, &B, &C, &m);
    n = A*B*C;
    for (int i=1; i<=n; i++) scanf("%d", &s[i]);  //讀生命值
    for (int i=1; i<=m; i++)                      //讀每次攻擊的范圍，用坐標表示
        scanf("%d%d%d%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i],&z1[i],&z2[i],&d[i]);

    int L = 1,R = m;      //經典的二分寫法
    while (L<R) {     //對m進行二分，找到臨界值，總共只回圈了log(m)次
        int mid = (L+R)>>1;
        if (check(mid)) R = mid;
        else L = mid+1;
    }
    printf("%d\n", R);  //列印臨界值
    return 0;
}

4. 差分習題

一維差分：poj 3263；hdu 6273，1121；洛谷P3406，P3948，P4552
二維差分：洛谷P3397，hdu 6514
三維差分：藍橋杯A組2018省賽“三體攻擊”