差分数组示例originArr:[1,2,5,7,23,4,78]differenceArr:[1,1,3,2,16,-19,74]D[n]=O[n]-O[n-1]eg:-19=4-231.特点1.1关系原数组的第n项==差分数组的前n项和\(byD[n]=O[n]-O[n-1],O[0]=D[0]\)=>\(O[n]=D[n]+O[n-1]\)=>\(O[n]=D[n]+D[n-1]+...+O[0]\)=>\(O[n]\)=\(\sum_{i=0}^nD[i]\)例如：\(7=1+1+3+2\)1.2前缀和（下标从0开始）原数组的前n+1项和==差数组的第i项值*(n-i+1)逐项累加\(\sum_{i=0}^{n}O[i]=\sum_{i=0}^n\sum_{j=0}^iD[i]\)=>\(\sum_{i=0}^nO[i]=D[0]+(D[0]+D[1])+...+(D[0]+D[1]+...+D[n])\)=>\(\sum_{i=0}^nO[i]=\sum_{i=0}^n(n-i+1)D[i]\)例如：\(1+2+5+7=1×(3-0+1)+1×3+3×2+2×1\)1.3区间运算由于对差分数组求和可以得到原数组的值前缀，如果将数字添加到sam的间隔e次，只需要差分数组区间的第一项为了保证加数后区间不变，需要在区间的最后一项减去数\(O[l]+x,O[l+1]+x...O[r]+x=>D[l]+x,D[r+1]-x\)eg:2~5+10originArr:[1,2,5,7,23,4,78]differenceArr:[1,1,3,2,16,-19,74]//同时将2-5加10originArr:[1,2,15,17,33,14,78]//15173314differenceArr:[1,1,13,2,16,-19,64]//1364//如果每一项都加1，那么只有差分数组的第一项需要加1可以维护原数组，所以当有频繁的区间加减运算时，使用差分数组可以将每次操作的时间复杂度控制在\(O(1)\)维护差分数组，一般使用下标作为值，真实值作为计数。由于下标从0开始，需要保留最后一位，所以差分数组的长度一般为最大值+22。应用中一般应用于某个状态对一定区间的均匀贡献值，最小值或最大贡献值或区间值差分数组的值一般初始化为0，统计每个状态不同区间的贡献值，前缀和解键：状态值/状态索引与区间贡献的对应关系2.1划分区间分成最少数量的组，并将其描述为多个闭区间。将相交的区间划分为一组，求最小划分数例[[5,10],[6,8],[1,5],[2,3],[1,10]]//除法[[2,3],[5,10]][[1,5],[6,8]][1,10]//结果为3将不相交的区间一分为二group=>当有交集时，增加一个新的组或加入其他非交集的组=>最小划分数==最大重叠子区间数例如，可以做不同的划分，但最小划分数必须等于最大重叠区间数有交集的交点必须在不同的组中，没有交集的区间在这些组中任意排列，达到最大区间差区间覆盖前缀和最大区间覆盖varminGroups=function(intervals){letmax=0letres=0letcur=0for(letiofintervals){max=Math.max(i[1],max)}//初始化差分数组letarea=newArray(max+2).fill(0)//区间+1中的所有元素表示覆盖计数for(letiofintervals){area[i[0]]++area[i[1]+1]--}//前缀并找到元素的最大覆盖数for(letiofarea){cur+=ires=Math.max(cur,res)}returnres};2.2使数组互补的最少操作次数说明给定一个长度为\(n\)的偶数整数数组\(nums\)，和一个极限数\(limit\)，求数组的最小变化次数阵列的互补性。互补：所有\(nums[i]+nums[n-i-1]\)的值相等\(eg:[1,2,2,3],sum=1+3=2+2=4\)limit:\(nums[i]\)\(\in\)\([1,limit]\)示例nums=[1,2,3,3]limit=41只需设置nums[2]=2即可通过\(sum=nums[i]+nums[n-i-1]\);\(nums[i]\)\(\in\)\([1,limit]\)\(=>\)\(sum\)\(\in\)\([2,2limit]\)假设\(x\)\(\in\)\([2,2limit]\),\(a=nums[i]\),\(b=nums[n-i-1]\)和\(a\)\(\leq\)\(b\),\(times\)是满足\(a+b=x\)的修改次数当\(x=a+b\),\(times=0\)当\(x\)\(\in\)\([1+a,a+b)\)\(\bigcup\)\((a+b,b+limit]\),\(次=1\)当\(x\)\(\in\)\([2,2limit]\)且不在上述范围内时，\(times=2\)从\(a+b\)展开：1，不需要修改，2，修改两者中间的一个，3，都需要修改\([1+a,a+b)\):b最小为1，\((a+b,b+limit]\)：a可以取到limit，修改单个数据超过这个范围不能满足条件，然后我们遍历每对数据，分别对上面3个不同的区间进行统计，最后我们可以得到每个\(sum\)需要修改的次数，每次取最小值就可以遍历对\(a+b\)可能出现的所有情况进行分类讨论，进行不同的加法运算。由于是中心扩散，可以先对最大范围+2，依次向内-1，这样可以用差值进行连续区间修改，全部遍历完成后，最后的结果是数组满足\(sum=每个\(sum\)[n-i-1]\)\((i\)\(\in\)\([0,\)\(\frac{n}{2}\)\(])\)建立所需的修改次数[1,2,3,3]4sumrange[2,3,4,5,6,7,8]count[0,0,0,0,0,0,0]13:[2,2,2,2,2,2,2][1,1,1,1,1,1,2][1,1,0,1,1,1,2]23:[3,3,2,3,3,3,4][3,2,1,2,2,2,4][3,2,1,1,2,2,4]最终结果：[3,2,1,1,2,2,4]可以看出，当sum=4或5时，只需要修改一次，最少修改次数为1。我们可以利用这个连续区间操作差分数组优化代码差分数组初始化建立长度\(2limit+2\)初始值为0数组区间修改每对修改不同区间的最小值求前缀的最小值sumvarminMoves=function(nums,limit){letmax=2*limit//下标的最大值为2*limit，长度为2*limit+1。由于差值维护需要最后一位，长度为2*limit+2letdiff=newArray(max+2).fill(0)//区间操作letn=nums.lengthfor(leti=0;i
