在了解差分之前，我們首先需要知道前綴和的概念。

前綴和簡單介紹：

對于一個數組A，要求出A[0]~A[i]的和，我們通常的做法是遍歷一邊，加起來。但是要求m組這樣的和，我們就要花費O(mn)的時間復雜度。顯然不合理。所以我們要用到動態規劃里的備忘錄思想，創建一個新數組B,B[i]記錄的是B[0]~B[i]的和。這個數組就是A的前綴和。

差分的概念：

有前綴和就有其逆定理。那就是假設數組A是一個前綴和數組，那么怎么求原數組呢B？答案是B[i] = A[i] - A[i-1] 這很好理解。這種算法可以被視為前綴和的逆運算。

現在我們獲得了差分的概念，讓我們看看怎么使用它吧。

如何使用：

差分的主要用處在于：

快速將序列A[l..r]的區間每個元素加上d。

正常加我們就需要不斷遍歷這一段數組。但是我們有了差分的概念，因此我們可以得到差分數組B[l]' = A[l] + d - A[l-1] = B[l] + d

B[r+1]' = A[r+1] -A[r] -d = B[r+1] - d

差分可以將在原序列上的?“區間操作”?轉化為差分序列上的?“單點操作”。

現在有了對一維數組的差分運算， 我們可以看看二維數組怎么操作。

二維差分：

二維差分要解決的問題是給原二維數組A的[x1,y1]~[x2,y2]處的所有元素加上d。

我們根據幾何關系可以得出以下公式

Bi,j = Ai,j - Ai-1,j - Ai,j-1, + Ai-1,j-1

結合前面文章中差分的用途，可以容易的想到，二維差分主要是用于快速將一個區塊中的所有元素都加上 d。

根據我們的公式我們很快得出一個結論：

對原數組A的[x1,y1]~[x2,y2]處的所有元素加上d等價于：

B[x1,y1] += 1

B[x1,y2+1] -= 1

B[x2+1,y1] -= 1

B[x2+1,y2+1] += 1

可以畫一張圖自己看看，推導很簡單

應用：

問題描述

小蘭擁有n*n 大小的棋盤，一開始棋盤上全是白子，小蘭進行了m?次操作，每次操作會將棋盤上某個范圍內的所有棋子的顏色取反（也就是白色棋子變為黑色，黑色棋子變為白色）。請輸出所有操作做完后棋盤上每個棋子的顏色。

輸入格式

輸入的第一行包含兩個整數 n,m，用一個空格分隔，表示棋盤大小與操作數。

接下來?m?行每行包含四個整數 x1,y1,x2,y2，相鄰整數之間使用一個空格分隔，表示將在 x1~x1行,y1~y2?列中的棋子顏色取反。

輸出格式

輸出 n?行，每行?n?個?0?或? 1?表示該位置棋子的顏色。如果是白色則輸出 0，否則1

樣例輸入

3 3
1 1 2 2
2 2 3 3
1 1 3 3

樣例輸出

001
010
100

代碼：

import java.util.Scanner;public class Main extends Base{public static void main(String[] args) {int n = I(),m = I();int[][] sum = new int[n+1][n+1]; //原數組int[][] diff = new int[n+2][n+2]; //差分數組for(int k=0;k<m;k++){int x1 = I(),y1 = I(),x2 = I(),y2 = I();//每次對差分數組4個位置操作diff[x1][y1]++;diff[x1][y2+1]--;diff[x2+1][y1]--;diff[x2+1][y2+1]++;}//由差分數組得到原數組for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){sum[i][j] = sum[i-1][j]+sum[i][j-1]+diff[i][j]-sum[i-1][j-1];if(sum[i][j]%2==0) print(0);else print(1);}print("\n");}}
}
class Base {static Scanner scan = new Scanner(System.in);static int I(){return scan.nextInt();}static <T> void println(T x){System.out.println(x);}static <T> void print(T x){System.out.print(x);}
}

sum[i][j] = sum[i-1][j]+sum[i][j-1]+diff[i][j]-sum[i-1][j-1];

這一行是?

Bi,j = Ai,j - Ai-1,j - Ai,j-1, + Ai-1,j-1求Ai,j的運算變形