三个月算法进阶--day82

RMQ问题

Range Minimum/Maximum Quary 区间最值查询问题

k « 1, k « 1 | 1

2 * n, 2 * n + 1

lazy_tag

区间更新，只更新到需要更新的区间的真子集，下次使用到时再消除标记

ST表

稀疏表，预处理使用二维数组f[a][b]存储[a, a + 2 ** b - 1]子区间的值

查询区间[l, r]，取s = log(r - l + 1)，则两个子区间[l, l + 2 ** s -1]和[r - 2 ** s + 1, r]可以覆盖[l, r]，即f[l][s]和f[r - (1 « s) + 1][s]两值的合并