蓝桥杯省赛最后一天冲刺！！
1、一维前缀和
例如：给你n个数组array， q次询问，让你求出 [L, R]的区间和。
题目：
给出数组 [1, 3, 7, 5, 2] ，求出 [2, 4] 这个区间的区间和。
分析：
我们求出前 n个数 的和 sum，求区间和，使用后面位置的数字和减去前面位置的数字和。
| indedx | 0 | 1 | 2 | 3 | 4 |
| array | 1 | 3 | 7 | 5 | 2 |
| sum | 1 | 4 | 11 | 16 | 18 |
（可以自己求和算一下，都很简单）
根据上面求和的过程，我们可以提取出不同数组的求和过程：
sum[i] = sum[i-1] + array[i] L>0
sum[0] = array[0] L=0求出前缀和之后，进行求区间和：
当 L> 0 时：
sum[2, 4] = sum[4] - sum[2-1] = sum[R] - sum[L-1] = 18 - 4 = 14
验证：7 + 5 + 2 = 14，
当 L = 0时:
sum[0, 3] = sum[3] = sum[R] = 16
验证：1 + 3 + 7 + 5 = 16
根据以上运算与验证过程，提取出求区间和的计算过程：
sum[L,R] = sum[R] - sum[L-1] L>0
sum[L,R] = sum[R] L=0代码实现：
我自己摸索着写的，可能会有更简洁的代码，不过我的水平只能写出这样了。
def profix_and(array, l, r):
# 定义前缀和
sum = [0 for _ in range(len(array))]
sum[0] = array[0]
for i in range(len(array)):
if i > 0:
sum[i] = sum[i - 1] + array[i]
# 计算区间差值
if l > 0:
return sum[r] - sum[l-1]
else:
return sum[r]
array = [1, 3, 7, 5, 2]
print(profix_and(array, 2, 4))实现了上面的例子，也可以自己指定数组和区间进行验证。
2、一维数组的差分
某个有n个数的数组，进行m个操作 [L , R] + value，进行询问后输出m次操作后的数组。
题目：
数组array=[1, 3, 7, 5, 2], 在 [ 2,4 ] 区间上加5, 在[ 1, 3 ]区间上加2, 在 [ 0, 2 ]区间上加3，进行这样三个操作。求出最后数组array的结果。
思路分析
利用差分数组将所有要进行的加减操作放在一个数组中，对差分数组算出前缀和，最后将差分数组的前缀和与原数组相加即为最后的结果。
手动计算：
| index | 0 | 1 | 2 | 3 | 4 |
| array | 1 | 3 | 7 | 5 | 2 |
| [2, 4]+5 | 1 | 3 | 12 | 10 | 7 |
| [1, 3]+2 | 1 | 5 | 14 | 12 | 7 |
| [0, 2]-3 | -2 | 2 | 11 | 12 | 7 |
差分数组
在实际代码中，把差分数组d全部都赋值为0即可，不需要计算出来
d[i] = array[i] - array[i-1]差分标记
[L,R] = d[L]+value, d[R+1]-value代码实现：
我自己写的代码，不一定是最优的，我觉得我能写出来就不错了哈哈哈
array = [1, 3, 7, 5, 2]
d = [0 for _ in range(len(array)+1)] # 定义差分数组
# 将差分标记封装到函数中
def add(l, r, v):
d[l] += v
d[r+1] -= v
# 进行加减操作
add(2, 4, 5)
# print(d)
add(1, 3, 2)
# print(d)
add(0, 2, -3)
# print(d)
# d的前缀和
sum_d = [0 for _ in range(len(array))]
sum_d[0] = d[0]
for i in range(len(sum_d)):
sum_d[i] = sum_d[i-1] + d[i]
# print(sum_d)
# 再将sum_d 与 array相加即为所求结果
for i in range(len(array)):
array[i] += sum_d[i]
print(array)家人们，学不完了啊啊啊啊，没事就这样吧，我真受不了了，把能做的都做上吧，尽人事，听天命吧，我希望我写的这些笔记能给我换个省三吧，不要求省一了，我想好好歇歇了，打算法比赛太累了，心力交瘁的。本来就是想备战蓝桥杯记录一下自己的学习，没有想到还收获了六百多个粉丝宝宝，算是意外之喜了。
等我考完蓝桥杯，我就要潜心学习了，先把自己自身的硬实力提升上去，再去做一些自己想做的一些项目。后续我基本上会每天更新自己的学习总结笔记的，每天学的东西可能都不一样，因为我想一出是一出，但是我会分好专栏的，大家如果有想要一起进步的，记得关注我哟~
最后祝大家都取得理想的成绩！！！相信自己！！！一定能行！！！
原文地址：https://blog.csdn.net/2301_78820199/article/details/137664731
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！