目录:
基本知识：
前缀和不一定是和，也可以是前缀积··· ···
前缀和是一种预处理算法，能大大降低时间复杂度。
前缀和的操作对象主要是数组。
前缀和主要是计算之前数组元素的值之和。在解决区域问题时，可以减少遍历操作，减少时间复杂度。
一维前缀和：
记原数组为a[n]，前缀和数组为b[n]。那么b[i]内存储的内容为a[1]~a[i-1]的和。
即b[1]=a[1],b[2]=a[1]+a[2],b[3]=a[1]+a[2]+a[3],… 或是b[1]=b[0]+a[1],b[2]=b[1]+a[2],…(数组下标从1开始)。
公式：b[i]=a[1]+a[2]+…+a[i] (或b[i]=b[i-1]+a[i])
| a | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
| b | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | … |
二维前缀和：
记原数组为a[n][m],前缀和数组为b[n][m]。
公式：b[i][j]=b[i-1][j]+b[i][j-1]+a[i][j]-b[i-1][j-1]
文字不宜表达，直接上表格！！！
版权声明：本文为struct_GS原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。