前缀和 学习笔记

模板及讲解

差分序列

差分序列$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]$配对,则有$|正数-负数|$高度种情况

环形积木大赛:

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

矩阵旋转$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

------ 本文结束 ------