PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

竣卜
5 years ago
Views:

1 差分与前缀和湖南师大附中 ruanxingzhi

2 区间加给定一个序列 a( 初值全为 0) 有很多次操作, 每个操作形如 : A l r k 将 a [l,r] 每个值加上 k. 最后输出整个数组复杂度要求 O(n). 允许离线

3 区间加代码 : ( 已经预先指定 a[0]=0)

4 区间加我们很自然地想到 : 如果我们知道每一个元素比前一个元素大多少, 我们显然可以推出整个序列 e.g. 已知 a 1 = 2 a 2 比 a 1 大 3,a 3 比 a 2 小 4. 那么可以推出 :a 2 = a = 5, a 3 = a 2 4 = 1.

5 区间加区间加 [l,r], 实际上是发生了这两件事 : a[l] 比前一个元素多了 k; a[r+1] 比前一个元素少了 k. 麻烦自己脑补一下 (: +k k

6 区间加我们用数组 p 表示刚刚的差值,p[i]=a[i]-a[i-1]. 那么 : 区间加 [l, r], 可以化为这两个操作 : p[l]+=k; p[r+1]-=k; 因此, 一次区间加只修改这两个元素 ; 最后利用 p 数组求出 a 数组, 即为答案

7 差分 Δa i = a i a i 1

8 差分在上面的题目中, 我们需要维护的数据是相邻两个数之差它有一个名字 : 差分令 p i = a i a i 1, 我们称 p 为 a 的差分数组

9 差分现在, 我们拿着 p 数组就能确定 a 数组 : a i 相当于 p [1,i] 这个前缀和想一想, 为什么? 你原本在 0 楼往上走了 3 楼, 再往上走了 4 楼, 再往下走了 2 楼, 你一共上了 3+4-2=5 楼因此你目前在 5 楼

10 区间加等差给定一个序列 a( 初值全为 0) 有很多次操作, 操作有两种, 强制在线 : - 区间加等差数列指定 [l, r], 指定等差数列 f 的首项和公差 a [l,r] 每一个元素加上对应的元素 : a [l] += f 1, a [l+1] += f 2, - 单点查询指定 x, 求 a x. e.g. 目前 a={1,2,3,3,3,3}, 给 [3,5] 加上首项为 2 公差为 1 的等差数列 A 变为 :{1,2,5,6,7,3}.

11 区间加等差显然 :a 区间加等差, 相当于 p 区间加常数端点单点修改 e.g. 目前 a={1,2,3,3,3,3}, 给 [3,5] 加上首项为 2 公差为 1 的等差数列原来的 p 数组 :{1,1,1,0,0,0} 之后的 p 数组 :{1,1,3,1,1,-4} A 变为 :{1,2,5,6,7,3}.

12 区间加等差区间加自然是给 p l+1,r 加上 d; p l 自然要加上 f 1 ; 那么右端点应该怎么改呢? 显然是要把刚才的操作复原我们给 p l 加上了 f 1, 给之后的 (r l) 个数加了 d. 因此 :p r+1 = f 1 + r l d.

13 区间加等差因此我们要解决的问题就很明显了维护 p 数组, 支持单点修改区间加显然可以用线段树解决思考题 : 如果要询问 a 数组的区间和, 怎么做? 提示 : 思路可以参考

14 区间加等差如果题目还要单点加, 应该如何实现? p x += k, p x+1 = k. 本质和区间加是一致的

15 乱七八糟求和给定序列 a, 有 n 次询问每次询问指定 [l, r]. 要你回答 : ans = e.g. 查询 [3,5], 则有 : r i=l ans = 3*a[3]+2*a[4]+1*a[5]. (r i + 1)a i

16 乱七八糟求和我们画个图 : 计数次数 ans = 5a 4 + 4a 5 + 3a 6 + 2a 7 + a 8 s 4 s 5 s 6 s 7 s 8 a 4 a 5 a 6 a 7 a 8 = 5a 4 + 4a 5 + 3a 6 + 2a 7 + a 8 +5s 3 5s 3 = s 4 + s 5 + s 6 + s 7 + s 8 5s 3 a i

17 乱七八糟求和求出 a 的前缀和数组 s, 接下来的询问就是 : - s 数组单点查询 - s 数组区间和查询我们再求出 s 的前缀和, 就能 O(1) 回答 s 的区间和查询综上, 本题 O(n) 预处理,O(1) 每次回答

18 区间加二次函数给定一个序列 a( 初值全为 0) 有很多次操作, 操作只有一种 : - 区间加二次函数指定 [l, r], 指定一个二次函数 f(x), 生成数列 {f 1, f 2 }. a [l,r] 每一个元素加上对应的元素最后输出 a 序列为了避免炸 int, 所有运算在模意义下进行

19 区间加二次函数做法 : 多阶差分令 p = Δa, r = Δp. 那么 :a 加二次函数, 相当于 p 加等差数列单点修改 ; p 加等差数列单点修改, 可以转化为 r 的单点修改和区间加 ; 再对 r 进行一次差分, 按照区间加那个做法就能解决问题每次修改达到 O(1). 最后求出 r, 通过 r 求出 p, 再通过 p 求出 a. 这件事是 O(n) 的

20 三个思想做了这么一些题, 我们大致可以归纳出三个思想 : 1. 差分降次, 前缀和升次关于常数的操作可以方便地完成 2. 知道 p 数组, 可以 O(n) 求出 a 数组 3. 知道 s 数组, 可以 O(1) 求出 a 数组的区间和

21 智障题今有 n m 的网格, 初始状态是空的有 k 次操作每次操作指定一个矩形 ( 给出四个顶点 ), 铺上地毯最后询问有多少个点没有被铺地毯二维差分, 二维前缀和,O(nm + nk). 差分 : 左上角加, 右上角减, 左下角减, 右下角加. 最后 p[x] y 的二维前缀和即为 a x [y].

22 思考题区间加二次函数改成区间加 k 次多项式不一定要用差分啊将函数 f(x) 平移成 f x l, 这样的话,a i 增加的值只与 i 有关, 而与首项无关这一步耗时 O(k 2 ). 将 a x 看作一个分段函数, 每个点都有对应的一组多项式的系数那么每次区间加就是给 a [l,r] 加上一组系数显然这又是区间加常数了, 用区间加的做法就能了事

23 思考题上面的做法瓶颈在于函数平移用 FFT 来加速平移, 每次操作可以达到 O(k log k). 至此问题解决每次操作 O(k log k), 最后 O(kn + kq) 统计结果代码细节 : 拿结构体来存系数, 重载一下加号然后就能直接套区间加的模板啦

24 思考题这题不要你最后输出 a 数组了要你支持在线查询 a i. 上面我们是用差分实现区间加系数的那现在就用线段树来加咯 O(k log k + k log n) 每次区间加 O(k log n) 每次查询

25 思考题现在 n 取操作仍然只有区间加多项式最后指定一些点, 查询 a i 的值. 扫描线即可复杂度与 n 无关了致谢 :riteme [

26 树上差分 a, b, LCA(a, b).

27 树上差分有一棵树, 点有点权有 m 个操作, 每个操作是 : - 链加指定 u, v, k, u 到 v 的路径上每个点点权加 k. 最后输出每个点的权值

28 树上差分 u v 的链加, 可以拆成两部分 :u LCA,v LCA. u LCA,v LCA 各加上 k, 然后 LCA 减去 k( 因为被加了两次 ) 也就是说, 我们需要实现 : 点到祖先的链加单点修改

29 树上差分如何实现点到祖先的链加呢? 思路和序列差分基本一致 u p 链加 k: flag[u]+=k; flag[dad[p]]-=k; +2 +1

30 树上差分最后对于每个点, 干下面两件事 : - 处理所有子节点 ; - 把所有子节点的 value 加上自己的 flag, 作为自己的 value 一遍 DFS 即可做到 +2 2 ( 也可以倒着拓扑排序, 从叶子推上来 )

31 链求和给定一棵 n 个点的树, 点有点权有 m 次询问每次询问 : 求树上两点之间路径上的点权和

32 链求和我们显然可以把 u v 拆成把 u LCA, v LCA. 即 :ans = d u LCA + d v LCA d[lca]. 现在的任务是 : 求出一个点到自己某个祖先的点权和我们很自然地想到前缀和前缀的定义修改成 : 点 x 到根节点经过的所有点前缀和记为 s. 显然 :d u anc = s u s dad anc.

33 链求和 ans = d u LCA + d v LCA d LCA. = s u s dad LCA + s v s dad LCA d[lca]. = s u + s v 2s dad LCA d[lca]. 我们懒得维护每个点的点权了, 式子可以改写成 : ans = s u + s v s[lca] s dad LCA. 只需要知道 s 数组, 就能 O(1) 回答 u v 的路径点权和

34 COUNT ON A TREE 给定一棵 n 个点的树, 点有点权有 m 次询问每次询问 : 求树上两点之间路径上第 k 大的点权强制在线 ( 这种题如果不强制在线, 会被树上莫队之类的万能算法水过 ) [BZOJ 题号 :2588]

35 COUNT ON A TREE 如果这棵树是一条链, 那显然是可持久化线段树模板题定义权值数组 :w i 记录 i 出现了多少次那么我们显然是在维护数组的每个前缀的权值数组这也是一种前缀和与差分的思想 i 在 [l, r] 中的出现次数, 就是 w r i w l 1 i. [l, r] 这个区间的权值数组, 就是 w r w[l 1]. 用线段树实现数组即可保证复杂度

36 COUNT ON A TREE 既然链状的情况可以这样干, 显然树上的也可以仍然把 u v 拆成 u LCA, v LCA. 显然 w u, LCA = w u w[dad[lca]]. 与链求和同理, 最后的式子是 : w u, v = w u + w v w LCA w[dad[lca]]

37 COUNT ON A TREE 子节点的前缀显然是从父亲那里继承过来的因此子节点的 w 由父亲节点的 w 派生出来用可持久化线段树实现就行了

38 差分的数学应用差分 <-> 求导前缀和 <-> 定积分

39 数学上的差分数学上的差分, 定义为 :Δf x = f x + 1 f(x). 为什么我们写代码的时候定义为 a i a i 1? 因为, 这样我们就用 p 1 记录了 a 1, 从而可以唯一确定 a.

40 差分的性质差分有一些有趣的性质比如, 请看 a n = n 3 的多阶差分 : (0, 1, 8, 27, 64, 125) //a -> (1, 7, 19, 37, 61) // 一阶差分 -> (6, 12, 18, 24) // 二阶差分 -> (6, 6, 6) // 三阶差分 -> (0, 0)

41 差分的性质为什么差分有这一项性质? 可以手动玩一下 x 3 x 1 3 = 3x 2 3x + 1, 变成二次多项式了这个性质可以用来找规律

42 差分的性质如果你感觉答案是关于 n 的多项式, 你可以试试这个办法 : 取数列的前几项, 不断地进行差分, 如果发现 k 阶差分所有项都是同一常数, 那么这个多项式就是 k 次的然后手动高斯消元一发, 就能找到 f(x).

43 有限微积分在之前的区间加二次函数一题中, 我们手动推出了 p r+1 需要如何修改 p 所加的等差数列的通项公式然而实际上, 这样做效率是很低的差分可以类比求导, 区间和可以类比定积分而且, 区间和也与定积分一样, 有类似的基本定理

44 有限微积分时间有限, 无法细讲请自行去了解相关知识关键词 : 下降阶乘幂有限微积分第二类斯特林数资料 : - 我的博客 ruanx.pw/post/ 有限微积分.html [ 入门 ] - 具体数学 [ 尤其安利这本书, 讲了很多有用的知识 ]

45 致谢 - 感谢各位看完了这份课件 - 感谢 riteme 教我区间加多项式 - 感谢 stdcall HJWJBSR 审查了这份课件

46 END 反馈与建议 : 请联系 ruanxingzhi@gmail.com

高等数学A

高等数学A 高等数学 A March 3, 2019 () 高等数学 A March 3, 2019 1 / 55 目录 1 函数三要素图像 2 导数导数的定义基本导数表求导公式 Taylor 展开 3 积分 Newton-Leibniz 公式 () 高等数学 A March 3, 2019 2 / 55 函数 y = f(x) 函数三要素 1 定义域 2 值域 3 对应关系 () 高等数学 A March