前言
最近比赛+做游戏+大学课，没多少时间搞这个，致歉
总之，就是前缀和和差分这个玩意，也是一种“空间换时间”的方法，至于什么是空间换时间，我也讲过了，链接在此：DP和背包问题|真理の小屋
前缀和
定义
最简单的说法，前缀和就是数列的前n项的和
更详细点，他就是一种预处理的方式，用来提前算出数列的前n项和
概念，定义这块本身就这么多，主要就是在于用法这一块上
用法
做法
先讲做法吧，这个就相当的简单，就比如说这样：
l=[1,2,3,4,5] #数组
for i in range(1,len(l)): #前缀和
l[i]+=l[i-1]
print(l)输出为：
[1, 3, 6, 10, 15]
那你们肯定会说：这么简单的玩意，那都会用到哪里呢？
就假设一种情况，如果需要查多次区间的和，
那如果按照暴力，就是需要每一次都需要重复的加之类
那最终肯定是会TLE的，
于是乎，就可以利用前缀和把这个玩意直接压缩成，只要把用右端点的前缀和减去左端点前一个位置的前缀和
于是得出以下代码：
n=int(input())
l=[1,2,3,4,5] #数组
for i in range(1,len(l)): #前缀和
l[i]+=l[i-1]
for i in range(n):
left,right=map(int,input().split()) #左右区间
print(l[right-1] - (l[left-2] if left > 1 else 0))补充
其实这只是一维的，再往上其实还有什么二维前缀和啊，多维前缀和还有树上前缀和之类的，但是这些变种的根本不还是从一维前缀和这一核心概念中衍生出来的变种，在我看来，目前只用讲这块就足够了，其他建议去看看这篇文章：前缀和 & 差分 - OI Wiki
至此，前缀和就主要适用于这些查询次数多的地方，当然，如果你们还是没办法理解，接下来便是示例
示例
就简单举个例子吧，洛谷题P8218 【深进1.例1】求区间和
这个就是一个很经典的前缀和题目，题目如下：
不想翻链接看这里
题目描述
给定由 n 个正整数组成的序列 a1,a2,⋯,an 和 m 个区间 [li,ri]，分别求这 m 个区间的区间和。
输入格式
第一行包含一个正整数 n，表示序列的长度。
第二行包含 n 个正整数 a1,a2,⋯,an。
第三行包含一个正整数 m，表示区间的数量。
接下来 m 行，每行包含两个正整数 li,ri，满足 1≤li≤ri≤n。
输出格式
共 m 行，其中第 i 行包含一个正整数，表示第 i 组答案的询问。
输入输出样例
输入 #1复制
4
4 3 2 1
2
1 4
2 3输出 #1复制
10
5说明/提示
样例解释
第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为 5。
数据范围
对于 50% 的数据：n,m≤1000；
对于 100% 的数据：1≤n,m≤105，1≤ai≤104。
这个就是差不多类似我前面所说的多次查询，我这里直接上完整代码吧：
n=int(input())
l=list(map(int,input().split()))
l0=[0]*(n+1)
for i in range(1,n+1):
l0[i]=l0[i-1]+l[i-1]
m=int(input())
for i in range(m):
left,right=map(int,input().split())
print(l0[right]-l0[left-1])前缀和这块就差不多了，接下来就讲差分了
差分
定义
同样，差分也和前缀和一样是预处理的，但你可以说差分是前缀和的逆运算之类的
通常来讲，这玩意主要用在需要大量修改的地方
用法
同样的，这里仅讲解一维差分，原因不再赘述
一维差分跟一维前缀和有点不同，具体表现为，需要额外搞一个列表之类
可惜的是，在python上，如果只限制使用标准库的情况下，我们需要自己写差分函数而不像c++是有std::adjacent_difference这样的函数作为辅助作用的，下面便是差分代码：
n=int(input())#需要修改的次数
l=[1,2,3,4,5,6,7,8,9] #被修改的列表
l0=[0]*10 #差分所需列表
for i in range(n):
a,b,c=map(int,input().split())#头，尾，值
l0[a]+=c
l0[b+1]-=c
for i in range(1,10): #像前缀和一样加起来
l0[i]+=l0[i-1]
for i in range(9): #把差分的列表混入这个列表里
l[i]+=l0[i]
print(*l) #输出结果正如你所见，现在修改是直接修改一次即可，也正是因为这样，差分才更适用于需要多次修改的情况之下
差不多讲完了，直接上示例吧
示例
不想翻链接的看这里
题目描述
该铁路经过 N 个城市，每个城市都有一个站。不过，由于各个城市之间不能协调好，于是乘车每经过两个相邻的城市之间（方向不限），必须单独购买这一小段的车票。第 i 段铁路连接了城市 i 和城市 i+1(1≤i<N)。如果搭乘的比较远，需要购买多张车票。第 i 段铁路购买纸质单程票需要 Ai 博艾元。
虽然一些事情没有协调好，各段铁路公司也为了方便乘客，推出了 IC 卡。对于第 i 段铁路，需要花 Ci 博艾元的工本费购买一张 IC 卡，然后乘坐这段铁路一次就只要扣 Bi(Bi<Ai) 元。IC 卡可以提前购买，有钱就可以从网上买得到，而不需要亲自去对应的城市购买。工本费不能退，也不能购买车票。每张卡都可以充值任意数额。对于第 i 段铁路的 IC 卡，无法乘坐别的铁路的车。
Uim 现在需要出差，要去 M 个城市，从城市 P1 出发分别按照 P1,P2,P3,⋯,PM 的顺序访问各个城市，可能会多次访问一个城市，且相邻访问的城市位置不一定相邻，而且不会是同一个城市。
现在他希望知道，出差结束后，至少会花掉多少的钱，包括购买纸质车票、买卡和充值的总费用。
输入格式
第一行两个整数，N,M。
接下来一行，M 个数字，表示 Pi。
接下来 N−1 行，表示第 i 段铁路的 Ai,Bi,Ci。
输出格式
一个整数，表示最少花费。
输入输出样例
输入 #1复制
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10输出 #1复制
6394说明/提示
2 到 3 以及 8 到 9 买票，其余买卡。
对于 30% 数据 M=2。
对于另外 30% 数据 N≤1000，M≤1000。
对于 100% 的数据 M,N≤105，Ai,Bi,Ci≤105。
直接上代码：
n,m=map(int,input().split())
p=list(map(int,input().split()))
lst=[0]*(n+2)
for i in range(m-1):
l,r=sorted((p[i],p[i+1]))
lst[l] += 1
lst[r] -= 1
for i in range(1,n):
lst[i] += lst[i-1]
count=0
for i in range(1,n):
a,b,c=map(int,input().split())
count+=min(a*lst[i],b*lst[i]+c)
print(count)至此，前缀和以及差分这块就差不多讲完了，若还有疑问，可以看看这俩者的对比
前缀和、差分俩者
前缀和、差分俩者区别
这俩的区别在于这几点：
一般来说，前缀和不需要为了预处理而选择额外开一个列表，而差分一般来说是需要的
前缀和在预处理阶段是一个列表为O(n)，而差分主要体现在修改时为O（1），整合的时候甚至是O（n）这种
在树的方面，前缀和或差分的处理方式有大不同
差分一定比前缀和好吗？
不一定，正如前文所述，差分的好处主要在于修改的时候，
如果说是需要[l,r]的和，多次查询的情况，那甚至还不如前缀和
但你也不能说前缀和一定比差分好，就这样
前缀和、差分能混用吗？
可以的，但据我所知，情况比较少，因为你需要的是需要多次查询、多次插入的情况，总之不推荐就是了
总结
前缀和和差分都是预处理的重要算法之一，都是概念简单、应用相对复杂的玩意
