)
二維字首和
假設我們給定義個二維數組a以及一個坐标(x,y）,我們把它左上角的所有元素的和叫做a在（x,y）的字首和，定義出這樣子的一個二維數組，那它就是字首和數組。
字首和數組求法:
sum[x][y]=sum[x-1][y]+sum[x][y-1]+a[x][y];
可以用面積來了解，（0，0）->(x，y)的面積=紅色圍住的面積+藍色圍住的面積—重疊部分的面積
求部分矩陣和
假設我給出字首和數組，給定兩個點（x1,y1）和（x2,y2），他們分别表示一個矩形的左上角和右下角（x1,y1）和（x2,y2），求兩點之間的矩形所有的數的和。了解的話看下圖，這裡給出具體公式：
all=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1,][y2]+sum[x-1][y-1];
二維差分
具體差分數組是怎樣定義的好像我也不懂，但這并不影響。
同樣的，二位差分數數組适用的條件也是有範圍的，我們在一維差分裡，我們應用差分數組的條件是在一個連續段上加上或減去某一個數。
在二維中，我們的條件是對一個矩形内的内容進行操作。
從圖中我們可以很清楚的看到，如果在x1，y1上加一個數c那麼它右下角的數都會加上c，那麼該怎麼辦呢，其實這也是容斥定理。我們隻需要減去右邊多加的部分和下邊多加的部分最後再加上重複減去的部分即可
是以，我們對二位差分數組進行的操作如下：
add(int x1,int y1,int x2,int y2,int c){
dif[x1][y1]+=c,dif[x2+1][y2+1]+=c;
dif[x2+1][y1]-=c,dif[x1][y1+1]-=c;
}
我隻要在圖中帶框的位置進行加減操作就不會影響到矩形外的元素了