随笔——倍增

l_h_l · 2023-02-17 23:05:09 · 个人记录

倍增：

板块1：倍增设计
其实就是模板：
设一开始跨度为 1，在位置 1，并对其他限制条件初始化。
每次看跨完后是否满足限制条件，满足，则跨度乘 2，并且位置加上跨度。
否则，跨度除以 2。
一直到跨度为 0 为止，位置即为答案。
因为答案有可能在最左边，所以有时比二分用时少。
并且树上(如树状数组)也会用到倍增，可比二分少一个log。
例题：天才ACM

板块2：ST 表：
是一种倍增类的算法思想，dp 的框架求解方式。
主要是用来求 RMQ 问题(静态区间最大值)。
用 f[i][j] 表示从 i 开始的后 2 的 j 个数的最大值。
所以询问时计算 max(f[l][k],f[r-(1<<j)+1][k] 即可覆盖整个区间。
其中 k 为 log(r-l+1)/log(2)。
初始化是让每个数 f[i][0] 为 0 即可。
然后得出状态转移方程与询问类似：

例题：模板ST表