# 前缀和

给定一个数组集合，前n个元素的总和可构成一个新的数据集合，这个集合就可称为前缀和；

例如：给定一个一维数组 nums，则可遍历求出前缀和数组 preSums，两者关系可表示为：

preSums[0] = nums[0]
preSums[1] = nums[0]+nums[1]
preSums[2] = nums[0]+nums[1]+nums[2]
...
preSums[n] = nums[0]+nums[1]+nums[2]+...+nums[n]

1
2
3
4
5

二维前缀和实际上就是一个矩阵内值的和，而矩阵又可以由两个行数或列数少一的子矩阵组合后，删去重合部分再加上右下角的值来构成，也就是以下式子：

$b_{x,y}=b_{x-1,y}+b_{x,y-1}-b_{x-1,y-1}+a_{x,y}$

前缀和是一种预处理，用于降低查询时的时间复杂度。