快速取得数组里某一段的和 “空间换时间”

思想：

O(N)->O(1)

• 预处理数组S
• S[i]代表数组内前i项的和；
• 则数组中L到R段的和就等于S[R]-S[L-1]

缺点：

• 只能处理静态数组，只能查不能改

二维前缀和

思想：

O(NM)->O(1)

求前缀和矩阵

• 选定位置左上角的元素和
• 容斥原理 S[x,y]=S[x-1,y]+S[x,y-1]-S[x-1,y-1]+a[x,y]

利用前缀和矩阵字某子矩阵和

• 设某子矩阵(x1,y1) (x2,y2)
• 该子矩阵和=S(x2,y2)-S(x2,y1-1)-S(x1-1,y2)+S(x1-1,y1-1)