一维，二维前缀和笔记

一维前缀和：

原来的数组是：a1，a2,a3......an 前缀和表示的是：Si = a1 + a2 + a3 + … + an 我们规定 S0 = 0 （好处理边界） 例如求：[l, 10] = S10 - S0 = S10 （统一表达式）

1. 如何求 Si Si = Si - 1 + ai 一重for 循环递推求
2. 前缀和的作用 求数组里面一段数的和 [l, r] Sr - Sl O(1)的时间复杂度

二维前缀和：

二维可以看成一个二维数组（二维矩阵），但是内存空间还是可以看成一维数组。 Sij 表示以 a00 和 aij 为矩形对角线的矩阵里面的元素的和。

1. 如何求 a00 到 aij 组成的矩阵的元素和。 两重for 循环外面是n 从 1 到 i 内层是m 从 1 到 j Sij = S（i-1）j + Si（j-1）- S（i-1）（j-1）+aij
2. 如何求 aij 到 axy 组成的矩形的意思和。 通过画图可以知道 Sxy - Sx（y - j）- S（x-i）y + S（x-i）(y-j) 通过画矩形来理解