算法基础：前缀和差分
问题引入：
给n个数a1 a2 a3 . an,q次询问，每次问你区间[L,R]数之和为多少.
解法1：暴力计算
最差复杂度：O(q*n)
当n > 1e4,q > 1e4的时候，代入发现
nq > 1e8,1秒之内跑不完.
这就要求我们寻找更优的算法.
前缀和：
第一步：预处理.一次循环求出序列的每一个前缀的和。用一个数组S存，S[i]代表下标从1~i的序列和
例如：对于序列a: 1 3 2 4（有四个前缀）
S[1] = 1,S[2] = 1+3=4;
S[3] = 1+3+2=6,S[4] = 1+3+2+4=10;
我们发现递推式：S[i] = S[i-1]+a[i]
第二步：查询区间和[L,R]
因为我们知道[1~R]的区间和等于
[1~L-1]的和 加上 [L ~ R] 的和.
即S[1~R] = S[1~L-1] + S[L~R]
所以区间[L,R]的和为：
S[L~R] = S[R] - S[L-1]
给一个长度为n的只含小写字母的字符串，q次询问，每次问你子串[L,R]之间，有多少个小写字母a
第一步：预处理.用一个数组S，一次循环求出每个前缀的a的个数。S[i]代表下标从1~i的前缀中a的个数.S[i] = ？
S[i] = S[i-1] + (str[i - 1] == ‘a’)
第二步:查询[L,R]之间有多少个a;
S[R] - S[L - 1]
思考合理性:
一句话说明:一个区间里a出现的次数 等于 将这个区间划分成若干个小区间，每个小区间里a出现的次数之和.
S[1~R] = S[1~L-1] + S[L ~ R]
所以:S[L~R] = S[1~R] - S[1~L-1].
再思考一个问题:前缀和是否能查询区间最大值.
ST表解决.(原理：倍增，动态规划)
二维前缀
问题引入:给你一个数字矩阵，给你q次询问,每次问(x1,y1)到右下角(x2,y2)所构成的子矩阵数字之和为多少 .
注:左上角为(1,1)
例如: 1 1 1 1
2 2 2 2
3 3 3 3
2 2 3 4 => 2+2+3+3 = 10.
暴力解决:最差复杂度O(n^3).
第一步:预处理.用一个二维数组S
S[i][j]代表 矩阵下标从1,1 累加到 i,j的前缀子矩阵和. — 找找状态转移
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i-1][j-1] + a[i][j]
第二步:查询区间和(从x1y1到x2y2)
差分:(前缀和的逆过程)
问题引入:给你n个数a1 a2 a3 … an.
m次操作:每次给区间[L,R]上的每个数 + c.
问你m次操作之后，每个数最终为多少.输出这个序列
方法①暴力模拟:复杂度O(n^2),太慢，不建议使用。
方法②差分：
先求差分数组d:d[i] = a[i] - a[i-1].(a为原数组)
例如: 原数组a: 1 3 2 4
差分数组d:1 2 -1 2 -4
注意:
①得到的差分数组d[1] = a[1]（相当于第一个数减0）
②差分数组最后比原数组多一个数（相当于0减最后一个数）
性质1:
对差分数组求前缀和得到原数组:
s[i] = d[1] + d[2] + … + d[i] = (a[1] - 0) + (a[2] - a[1]) + (a[3] - a[2]) + … + (a[i] - a[i-1]) = a[i]
再对s[i]作前缀和得到原序列的前缀和。
性质2:对差分数组d[L] += c,d[R+1]-=c 等效于原序列区间[L,R]所有值+c.
①d[R+1] = a[R+1] - a[R] - c,
②d[L] = a[L] - a[L-1] + c
解释:假设原数组[L,R]都+c,那么对于差分数组来说，就只有d[R+1] 与 d[L]这两个值要变,其他位置的差分值都不变(因为原数组的相对大小不变)
应用性质1(从L-1开始推):
③S[L-1] = a[L-1]
S[L] = S[L-1] + d[L] => S[L] = a[L] + c(将②③代入)
S[L+1] = S[L] + d[L+1] => S[L+1] = a[L+1] + c
…(c一直往下传递，直到碰到d[R+1],将这个c抵消)
这样，我们就成功的在O(1)时间内将区间[L,R]上所有值都+c.m次操作复杂度O(m),最后O(n)时间内可以得到原数组(将差分数组求前缀和)
回到刚才那个题：
第一步：读入n个数,用a数组装着
第二步：预处理求出a数组对应的差分数组d.
第三步:对于每次操作,给出L,R.
使d[L] += c,d[R+1]-=c
第四步:得到最终d数组之后，求一遍前缀和，获得原数组，输出
思考一个问题:如果修改操作和查询操作混合在一起
，差分的思想是否还派得上用场呢?
*线段树，树状数组解决
总结:
①前缀和与差分 实际上是一对逆运算
②差分前缀和实际上是一种预处理技术，不支持修改.若要修改，需要使用更高级的数据结构。