ST表与RMQ问题 2018年12月4日2020年2月17日 zhaoyuweijsnt@163.com 评论 ST表思想用来解决区间最值查询问题。与线段树相比，ST表只支持离线问题，但是在经过$O(n \lg n)$的预处理之后，ST每次询问的复杂度是$O(1)$的，而线段树的询问是$O(\lg n)$的，所以ST适合解决规模更大的离线问题。 感谢 ketchuppp 同学纠正了本文的错误！ 继续阅读