差分配列差分配列基本内容定义差分配列形式描述应用与暴力解法比较解决过程差分配列具体问题的主题解题思路求解步骤代码
差分配列的基本
首先，差分配列看起来像个大名词，实际上不是排列吗？ 解决差分配列问题的思想是实际制作排列，并维护该排列。
定义：对于已知有n个要素的离线数列d，可以创建记录各个项与上一项的差分的差分配列f。 很明显，f[1]=d[1]-0=d[1]； 对于整数i[2，n]，设为f[i]=d[i]-d[i-1]。
差分配列形式差分配列元排列和差分配列形式如下图所示。
说明：差配列各项为原数组当前项 - 原数组前一项
此图中的差分配列值来源于：
diff list [3]=list [3]-list [2]=4-2=2diff list [2]=list [1]-list [2]=0diff list [1]=list
与暴力解法相比，对于以上问题的解决方法，如果使用暴力的遍历排列，当然会得到理想的结果。但是在时间复杂度上，暴力的时间复杂度为o(n )，而差分配列可以使用时间复杂度3358www.Sina.com/，因此差分配列解法实际上是暴力解法的http://ww.Sina
解决过程以给定的数组为list，对区间[l，r]上的各个项目同时求出1
数组list包含区间[l，r]
经过创建差分配列diffList、创建diffList [l ] 1、将diffList [ r 1 ]- 1前缀到数组diffList、并将差分配列的各个项目添加到list的这五个步骤，将区间[ l，R]的各个项目添加到list中
为什么这么说，是因为如果想把l-r的所有项都设为1，把差分配列的所有项都添加到原数组中就可以了。 因为如果差分配列的所有项都是原始数组的当前项与原始数组的上一项之间的差分，那么只要找到差分配列就可以了。
要找到差分配列，可以这样做。
得到差分配列
应用差分配列的具体主题其次，给出了在非常简单的差分配列应用例题中差分配列如何优化区间的加减。
主题说明leetcode 1109 .航班预订统计
这里有n个航班，分别从1到n编号。
有航班预约表bookings。 表中第I条的预约记录bookings[i]=[firsti，lasti，seatsi]意味着从firsti到lasti (包括firsti和lasti ) )的每班航班都预约了seatsi座位。
请返回长度为n的数组回答器。 其中，answer [ I ]是航班I上预订的座位总数。
O（ n ）- O (1 )
1=n=2 * 10^4
1=bookings.length=2 * 10^4
bookings[i].length==3
1=firsti=lasti=n
1=seatsi=104
解决问题有两种想法，
第一个是暴力。 这个问题时间很多，可以通过暴力设法度过。 第二个是差分配列。 几乎没有额外的操作，几乎可以说是差分配列的模板问题。 解决问题的步骤是用暴力的方法，因为没有大脑，所以解决不了
说明差分配列。
建立长度为n的数组，对给定数组bookings的前两项进行差分操作，对差分操作后的数组进行前n项前缀和代码暴力求解
//暴力的class解决方案{ public int [ ] corpflightbookings (int [ ] bookings，int n ) ) seats=newint )； for(intI=0； ibookings.length； I ) for(intI1=Bookings[I][0]-1； i1bookings[i][1]； i1 ) { seats[i1]=bookings[i][2]； } }返回集； }暴力运行时间：
差分配列
//差分配列class solution { public int [ ] corpflightbookings (int [ ] bookings，int n ) )/1 .创建长度为n的数组int[]seats=newings ibookings.length； I ) )/2 .在给定数组的bookings的前两个上执行差分操作seats [ bookings [ I ] [0]-1 ]=bookings [ I ] [2]； if(bookings[I][1]n ) seats [ bookings [ I ] [1]-=bookings [ I ] [2]； } } //3.将差分操作后的数组与前n项前缀for(intI=1； in； I ) { seats[i]=seats[i-1] seats[i]； }返回集； }差分配列的执行时间
以上是我对差配列的理解，欢迎大人物斧正