前缀和 学习笔记

模板及讲解

差分序列

差分序列$f$记录$a[i]-a[i-1]$的值,$a$为原序列
那么根据定义可以发现差分序列的前缀和就是原序列的数
那么输入$a,b$, 我们让$f[a]+1, f[b+1]-1$就可以构造出差分序列
这样可以实现$O(1)$区间修改,$O(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

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