前言
这是笔者备考蓝桥杯自己做的学习相关内容，或有不准确，欠妥的部分，请谅解，如有问题，欢迎评论，也欢迎在评论区留言备考蓝桥杯的相关心得，寻找一同学习的学习搭子，加油同志们！
一、一维前缀和
1、一维前缀和的定义与性质
定义：sum[i]表示数组a的前i个数的和，即为前缀和，一维前缀和习惯从0开始
sum[i] = a[0] + a[1] + ... + a[i]
性质：可以在O（1）的复杂度内进行一个区间的判断、求值
#递推求前缀和
sum[i] = sum[i-1]+a[i]
#前缀和可以用来求一个区间的
a[l] + ... + a[r] = sum[r] - sum[l - 1]2、一维前缀和的实现
（1）实现方式——循环
##求前缀和的函数
def get_presum(a):
n = len(a)
Sum = [0] * n
Sum[0] = a[0]
for i in range(1,n):
Sum[i] = Sum[i - 1] + a[ i ]
return Sum
##在O（1）的时间复杂度中获取一个a[l] + .... a[r]
def get_sum(sum,l,r):
if l==0:
return sum[r]
else:
return sum[r]-sum[l-1]
a = [1,2,3,4,5]
sum = get_presum(a)
print(sum) （2）实现方式—迭代器
ps：注意，迭代器默认是从0开始，如果你构建的数组想要从1开始，请先进行调整
##迭代器构建前缀和
from itertools import accumulate
def get_presum_iter(a):
sum = list(accumulate(a))
return sum
##在O（1）的时间复杂度中获取一个a[l] + .... a[r]
def get_sum(sum,l,r):
if l==0:
return sum[r]
else:
return sum[r]-sum[l-1]
a = [1,2,3,4,5]
sum = get_presum(a)
print(sum) 二、二维前缀和
1、二维前缀和的定义与性质
定义：二维前缀和的下标习惯从1开始，所以一般情况下，会采取在最左边和最上面留出一列、一行[0]，某一个点的前缀和是：以这个点向左向上围成的一个矩阵的和
sum[i][j] = a[1][1]+...+a[1][j]
+ a[2][1]+...+a[2][j]
+ ...
+ a[i][0]+...+a[i][j]
性质：求一个矩阵的内和
如下图所示，现在有一个二维矩阵，我现在想求黄色区域的所有数的和，我要怎么做？
（请你思考一下呢？）
这里，我们用(x2,y2)-(x1,y1)来代表黄色区域
(x2,y2)-(x1,y1) = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]
其中：sum[x2][y1-1]是紫色区域 ，sum[x1-1][y2]是粉色区域，有一个区域多减去了，再给它加回来
2、二维前缀和的实现
def get_presum(a):
## 获取行数
n = len(a)
## 获取列数
m = len(a[0])
## 构建一个前缀和数组
sum = [[ 0 ] * ( m + 1 ) for _ in range( n + 1 )]
for i in range( 1 , n + 1 ):
for j in range( 1 , m + 1 ):
## PS：这里用a[i-1][j-1]是因为a的坐标是从0开始的，但是i，j是从1开始的
## 简单来说就是，没有办法取到a[0][*]的一行以及a[*][0]的一列
## 根本原因是因为，sum数组在最上方和最左边增加了[0]行（列）
## 但是a没有添加上
## 如果出现题目，需要自己输入，可以这样，满足上面添一行0，左边添一列0：
## for i in range(1,n+1):
## a[i] = [0] + list(map(int,input().split()))
sum[i][j] = sum[ i - 1 ][ j ] + sum[ i ][ j - 1 ] - sum[ i - 1 ][ j - 1 ] + a[ i - 1 ][ j - 1 ]
return sum
a = [[ 1, 2, 3, 4],[5, 6, 7, 8]]
sum = get_presum(a)
print(sum)