知识库 · 文字讲解,AI 整理
前缀和与差分
前缀和:O(1) 区间求和
LaTeX
$$S_0=0,\qquad S_k=\sum_{i=1}^ka_i,\qquad \sum_{i=l}^ra_i=S_r-S_{l-1}.$$
$O(n)$ 预处理一次,之后每次查询 $O(1)$。前缀数组开 $n+1$ 长、$S_0=0$,从头开始的区间就不用特判。
差分:O(1) 区间加
给闭区间 $[l,r]$ 加上 $v$,只改两个位置:
LaTeX
$$d[l]\mathrel{+}=v,\qquad d[r+1]\mathrel{-}=v.$$
所有操作做完,对 $d$ 求一次前缀和就还原出更新后的数组。前缀和与差分是一对互逆的离散运算——离散的积分和求导,对应 望远镜求和。
和为 T 的子数组有几个
$S_i-S_j=T\iff S_j=S_i-T$。用 哈希表 记住每个前缀和出现过几次,扫到 $i$ 时查一下 $S_i-T$ 出现过几次,再把 $S_i$ 的计数加一,期望 $O(n)$。初始化时空前缀和 0 要记为出现 1 次,否则会漏掉从头开始的子数组。
怎么选
高频区间查询用前缀和;批量区间修改用差分;按键累计状态用哈希;有重复子问题、转移明确用 动态规划。
用到它的地方
- 知识库 哈希表
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。