差分配序列定义：差分配序列是指从一个序列中的后一项减去前一项以形成新的序列
eg:
原来的排列5 4 7 2 4 3 1
从后者项中减去前一项，第一项保持不变
5，4-5，7-4，2-7，4-2，3-4，1-3 )
差分配列：5 -1 3 -5 2 -1 -2
性质：求最主要性质3360差分配序列前缀和结果与原序列相等
用上面的样品
对差分配列求前缀和
五，四，七，二，四，三，一
用途：差分配序列主要针对序列部分区间同时加上或减去一个数
举个例子
原排列： 5 4 7 2 4 3 1
序列下标：0 1 2 3 4 5 6
对于下标1~4的要素，必须同时加上1
也就是说，将原来的排列设为5 5 8 3 5 3 1
最朴素的想法是从下标1到4使(a(1)~a(4) )进行遍历
这样的复杂度是o(n )级，这里以o(n)为主题
区间长度为1w或1亿的元素时，需要操作吗？
这种情况下使用差分配列进行
差分配列：5 -1 3 -5 2 -1 -2
下标------ 0 1 2 3 4 5 6
针对下标为1的要素，针对下标为5的要素进行减法操作
获得新的差异分配列：5 0 3 -5 2 -2 -2
对此，要求前缀和5 5 8 3 5 3 1
可以看出，下标1￣4的要素均进行1次操作，2次操作即可解决问题
也就是说，仅凭o(2)的复杂性就可以解决o ) n )的问题
为什么会产生这样的效果呢？
其实这是差分配列的定义和性质造成的。 他从后者的项中减去前者的项，而且只有求前缀和才成为原来的数组，所以求前缀和时只要加减其中一个要素，
之后的价格又涨又降。
因此，为了增减a[n]~a[m]区间，
a[ m+1]需要相反加减运算，a[ n]需要3358www.Sina.com/
例题海底高铁洛谷
相同
首先有n和m，也就是n个城市，要想去m个地方，说明m个地方可以重复到达
第I座城市和第I座城市之间有铁路，有两种购票方法。 其中一张：直接成本票使用Ai，其二张：先购卡，购买打折票使用Bi Ci。 主题中展示了与第I段铁路不同的费用Ai Bi Ci
题目分析
根据提示的城市路线，可以求出通过各条铁路的总次数，用总次数计算出两种费用分别需要多少，取最小费用，依次计算出所有通过铁路的总费用。
如何求出通过各铁路的总次数？
这是用了我们的差分配列
开始排列也就是说0 0 0 0 0 0 0 () 8个城市，7段铁路，下标从1开始) ) )。
开始差分配列也是0 0 0 0 0 0 0
给出课程1372
从1号城市到3号城市需要通过第1段和第2段铁路时，差分配列a [1] a [3]
1 1 0 0 0 0 0 (原排列) )。
1 0 -1 0 0 0 0(差异分配序列) ) )。
从3号城市到7号城市需要通过第3、4、5、6、7段铁路。 a[3]，a [7]
1 1 1 1 1 1 0
1 0 0 0 0 0 -1
从7号城市到2号城市需要经过第6、5、4、3、2段铁路。 a[2]，a [7]
1 2 2 2 2 2 0
1 1 0 0 0 0 -2
如果不知道，一定要标上城市号和铁路号
通过上述模拟，有规律地从x到y得到cnt[min[x，y]]、cnt[max(x，y )即城市号小加法、城市号大减法，解决问题时用cnt存储差分配列，最后用cnt
解题思路
# includeiostreamusingnamespacestd； 常数int maxn=1e510； int n，m； int cnt[maxn]； 龙龙vis [ maxn ]，ans； //因为数据可能太大，所以长时间结构节点{长时间a，b，c； //不同费用} e[maxn] //铁路段longlongmymin(longlongx，long long y ) { return xy？ x:y； (}int main ) ) { cinnm； int x，y； cinx； //起点//差分配列for(intI=1； im； I ) ({ ciny； //终点CNT[min(x，y ) ] CNT[max(x，y ) ]----； x=y； //终点求出新起点(//前缀和for (inti=1； in； I ) { vis[i]=vis[i-1] cnt[i]； //最终要求施加for (inti=1； in； I )扫描(' % d % d ) d )，e[i].a，e[i].b，e[i].c )； ans=mymin(vis[I]*e[I].a，vis[i]*e[i].b e[i].c )； } coutansendl； 返回0； }