前綴和

1、一維前綴和

公式：
1、預(yù)處理前綴和：S[i] = a[1] + a[2] + ... a[i]
2、求區(qū)間和：a[l] + ... + a[r] = S[r] - S[l - 1]

2、二維前綴和：

1、前綴和：s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)為左上角，(x2, y2)為右下角的子矩陣的和為：
2、求區(qū)間和：S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

差分

1、一維差分

常見(jiàn)場(chǎng)景：給區(qū)間[l, r]中的每個(gè)數(shù)加上c：d[l] += c, d[r + 1] -= c

公式：d[i]=a[i]-a[i - 1]

2、二維差分

給以(x1, y1)為左上角，(x2, y2)為右下角的子矩陣中的所有元素加上c：

公式：

b[x1][y1] +=c;
b[x1][y2 + 1] -=c;
b[x2 + 1][y1] -=c;
b[x2 + 1][y2 + 1] +=c;