- 区间和问题 - 前缀和
- RMQ问题 - ST表
- 区间修改 - 差分
- 单调队列 - 滑动窗口最值
- 单调栈 - 每个数后面第一个比它大/小的元素
- 双指针
令sumi=x=1∑iax
则x=i∑jax=sumj−sumi−1
令sumi,j=x=1∑iy=1∑jax,y
令 fi,j 为从 ai 开始的 2j 个元素的最大值。则有：
fi,j={aimax(fi,j−1,fi+2j−1,j−1)j=0j>0
显然可以 O(NlogN) 预处理出 f 数组。
对于区间 [i,j]，长度 len=j−i+1，区间最大值即：
max(fi,⌊loglen⌋,fj−2⌊loglen⌋+1,⌊loglen⌋
令di=ai−ai−1
则ax=i=1∑xdi
如果维护一个数组的差分数组 d，给 di 加一就相当于给 ai∼an 都加了一。如果需要给 al∼ar 都加上一，就可以用给 dl 加一，dr+1 减一来实现。
因此如果需要处理大量的区间加法操作，就可以只在原数组的差分数组上实现，每次操作都只要 O(1) 的时间即可完成。最后把最终的差分数组还原回原数组即可。
