1.一维前缀和

S[i] = a[1] + a[2] + ... a[i] //求s[n]
a[l] + ... + a[r] = S[r] - S[l - 1]//求l-r的序列和

2.二维前缀和

S[i, j] = s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]