如何进行查询静态区间最大值

· · 算法·理论

对于 10^5 的级别，我们如何查询区间最大值呢？

ST表

经典算法，有模板题。

具体的，维护 f_{i,j} 为 a_i 至 a_{i+2^j-1} 的最大值。查询时，设 k=\lfloor log_2(r-l+1)\rfloor，取 \max(f_{l,l+k},f_{r-2^k+1,k})。

空间 O(n\log_2n)，时间预处理 O(n\log_2n)，查询 O(t)。

线段树&树状数组

也很模板，特别的树状数组只能初始化，而线段树支持修改，但这里不需要。

空间 O(n)，时间预处理 O(n)，（树状数组可以做到预处理 O(n)），查询 O(t\log_2n)。

平衡树

使用 Splay 或 FHQ Treap 将区间提出来，并维护最大值。

空间 O(n)，时间预处理 O(n)，查询 O(\log n)。

分块

也是很板的了，分成 \sqrt{n} 块，整块直接取最大值，边缘小块暴力。

空间 O(n)，时间预处理 O(n)，查询 O(t\sqrt{n})。

莫队

没想到吧。

将询问离线，删除比较麻烦，可以使用回滚，或者使用值域分块。

空间 O(n)，时间 O(n\sqrt{n})。

主席树

大柴小用。

具体的，rt_i 为前 i 个元素在值域上建的树，查询时把 l 到 r 的树抠出来，能往右就往右走。

空间 O(n\log_2n)，时间 O(n\log_2n)。