一句话理解
ST 表倍增预处理 f[k][i]：从 i 开始 2^k 长度的最值。
为什么要学
O(n log n) 预处理。
讲解
f[k][i]=max(f[k-1][i], f[k-1][i+2^{k-1}])。
例子
区间倍增。
常见错误
- k 循环顺序错。
- 第二维大小 n 不够加 2^k。
第 434 课
倍增预处理
🟠 进阶 约 10 分钟
练习 做完再看下一课
ST 表预处理是倍增的。
进度保存在本机浏览器里。
左右方向键也可翻课
第 434 课
ST 表倍增预处理 f[k][i]：从 i 开始 2^k 长度的最值。
O(n log n) 预处理。
f[k][i]=max(f[k-1][i], f[k-1][i+2^{k-1}])。
区间倍增。
ST 表预处理是倍增的。
左右方向键也可翻课