所以 O(n) 次单点 chkmax，O(nsqrtn) 次求区间 max 怎么做？

· · 算法·理论

irris 教的，感觉非常厉害！

标题就是要你实现 \Theta(\sqrt n) 单点 chkmax，\Theta(1) 区间求 max。

考虑 ST 表，那肯定就很疑惑这个东西怎么和根号扯上关系啊？？？

你考虑很暴力的做法，就暴力在 ST 上修改，第 i 层修改 \Theta(2^i) 个信息，单次 chkmax 需要 \Theta(n)，然后就寄了。

呃那考虑套一个分块，维护块内 ST 表和块间 ST 表，显然两者都只需要修改 \Theta(\sqrt n) 个信息，然后就做完了！