声明(叠甲)：鄙人水平有限，本文为作者的学习总结，仅供参考。 1.RMQ介绍 在开始介绍ST表前，我们先了解以下它以用的场景RMQ问题。RMQ(RangeMinimum/MaximumQuery)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题，其主要的特征是查询的区间是静态的。在上一篇关于线段树的文章中我们解决了动态的区间的维护，先是进行O(nlog(n))时间负载度的建树预处理，然后就能以O(log(n))的时间复杂度进行维护与查询。对于RMQ问题来说线段树也是能...