模板及讲解

差分序列

差分序列$f$记录$a[i]-a[i-1]$的值，$a$为原序列
那么根据定义可以发现差分序列的前缀和就是原序列的数
那么输入$a,b$, 我们让$f[a]+1, f[b+1]-1$就可以构造出差分序列
这样可以实现$O(1)$区间修改，$O(n)$单点查询(这里可以用数据结构维护)

差分序列性质：

1、差分序列前缀和$S_i$是原序列的数$A_i$
2、原数组所有数等于 0 等价于差分序列为 0
3、$f[a]+1, f[b+1]-1$等同于在原数组区间修改

1、修改区间操作
BZOJ 1651

2、差分序列性质解题

积木大赛：区间减为0最小修改次数。

差分序列正负数配对消去(相当于$a[l]+1, a[r]-1$)，剩余正数与$a[0]$配对)
原数组所有数等于 0 等价于差分序列为 0

IncDec Sequence (Bzoj 3043)：区间增/减后所有数相等的最小修改次数，以及最后高度的可能情况。

原数组所有数等于 0 等价于差分序列为 0 ，这里只要相同则对$a[1]$无要求
差分序列正负数配对消去(相当于$a[l]+1, a[r]-1$)，剩余正数/负数与$a[1], a[n+1]$配对)
求可能情况则可以认为剩余正数/负数可以与$a[1], a[n+1]$配对，则有$|正数-负数|$高度种情况

环形积木大赛：

找到一个最小值断环成链即可用上面的差分方法

3、差分与前缀和 (by ruanxingzhi 差分与前缀和)

差分降次，前缀和升次，对于前面加速其实就是将数组降次后，再升次得到原数组

区间$[l,r]$加一次函数(等差数列)：

将数组差分后，在$a[l]+=首项$，后面$a[l+1,r]+=d$，$a[r+1]-=首项+(r-l)d$
显然这个可以用线段树维护。

区间$[l,r]$加二次函数：

考虑多阶差分。
将二次函数差分后得到一次函数。
一次函数差分后得到常值函数。
然后用线段树维护即可。

找规律：

若觉得答案为关于$n$的多项式，那么可以取其前几项然后不断差分，如果发现$k$阶差分所有项都是同一常数，那么这个多项式就是$k$次的。

手动高斯消元找到$f(n)$，大概是用一阶差分来高斯消元

矩阵旋转$45^{\circ}$

输入的时候按正常顺序输入，但存储时要存到$(i+j-1,n-i+j)$，这个公式退推一下就能出来

常见题型

1、差分序列(一维前缀和)
Q：区间修改单点查询。
解：见解析
例题：BZOJ 1651
2、树上差分序列(树上前缀和)
Q：在树上修改某一条路径的值。
解：我们让$f[u]+1, f[v]+1, f[LCA(u, v)]-2$，这样做以后在树上的前缀和$\sum_{k\in son(i)}{f[k]}$就是节点$i$的值
例题：NOIP2015 D2 T3
3、差分序列约束区间
Q：某区间必须小于某个值。
解：对于每个约束$a,b$，我们使$f[a+1]–,f[b]++$，这样可以保证$a,b$之间的元素严格小于$a,b$
例题：BZOJ 1635
4、二维前缀和
Q：查询某个矩阵的子矩阵的和
解：容斥原理，和二维树状数组的求法差不多
例题：NOIP2016 D2 T1
5、旋转矩阵后前缀和维护
Q：在一个矩阵中找出一个分值最大的斜矩阵
解：把矩阵旋转$45^{\circ}$，然后就可以在水平求前缀和了
例题：计蒜客NOIP模拟赛-1 Day1 T1