简介
RMQ(range minimum/maximum query),即区间最值查询。
解决RMQ问题主要有两种方法:ST表(sparse table)和线段树(segment tree),本文主要讲ST表。
ST表适合解决静态区间最值查询,即下面的问题:
给定$n$个数,进行$m$次询问。对于每次询问,你都需要回答区间$[l, r]$中的最小值或最大值。
如果暴力做法,每次对区间$[x, y]$扫描一遍,肯定是过不了的,所以我们需要引入ST表。
ST表可以实现$O(n \log n)$的预处理和$O(1)$的查询。