前綴和

原數組	x0	x1	x2	x3	x4	x5
前綴和數組	x0	x0+x1	x0+x1+x2	x0+x1+x2+x3	x0+x1+x2+x3+x4	x0+x1+x2+x3+x4+x5
前綴和數組代數形式	x0’	x1’	x2’	x3’	x4’	x5’

計算原數組某區間的和 sum[x1,x2,x3]
利用前綴和計算
x3'-x0' = x0+x1+x2+x3-x0 = x1+x2+x3

差分數組

	x0	x1	x2	x3	x4	x5
原數組	x0	x1	x2	x3	x4	x5
差分數組	x0	x1-x0	x2-x1	x3-x2	x4-x3	x5-x4
差分數組代數形式	x0’	x1’	x2’	x3’	x4’	x5’

計算原數組某區間所有元素同時增加 inc之后的數組

	x0	x1	x2	x3	x4	x5
原數組區間[1,4]增加inc	x0	x1+inc	x2+inc	x3+inc	x4+inc	x5
差分數組	x0	x1-x0+inc	x2-x1	x3-x2	x4-x3	x5-x4-inc

步驟	x0	x1	x2	x3	x4	x5
1	x0	x1-x0+inc+x0
2	x0	x1+inc	x2-x1+x1+inc
3	x0	x1+inc	x2+inc
4	x0	x1+inc	x2+inc	x3-x2+x2+inc
5	x0	x1+inc	x2+inc	x3+inc	x4-x3+x3+inc
6	x0	x1+inc	x2+inc	x3+inc	x4+inc	x5-x4-inc+x4+inc
7	x0	x1+inc	x2+inc	x3+inc	x4+inc	x5

可以看到最終與原數組區間[1,4]增加inc的結果一樣

【結論】
原數組區間[l, r]的元素增加 inc
等價于其差分數組元素 d[l] + inc和元素 d[r] - inc之后的前綴和數組

力扣-1109. 航班預訂統計