Lougu-3865-【模板】ST表(倍增写法)

给定一个长度为 N N 的数列,和 M M 次询问,求出每一次询问的区间内数字的最大值。

题目链接

Lougu-3865-【模板】ST表

输入输出格式

输入格式:

第一行包含两个整数 N , M 分别表示数列的长度和询问的个数。

第二行包含 N N 个整数(记为 ai a i),依次表示数列的第 i 项。

接下来 M行,每行包含两个整数 li, ri,表示查询的区间为 [ li, ri]

输出格式:

输出包含 M M行,每行一个整数,依次表示每一次询问的结果。

输入输出样例

输入样例1:

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出样例1:

9
9
7
7
9
8
7
9

题解

显然这是一道ST表的模板题。~ 但是重点在于倍增的思想。相比于二分,我们每次对于一个序列进行÷2的折半查找,而倍增则是每次对于序列×2的查 找。对于倍增一个很好的运用就是RMQ。~(在?为什么不是LCA)~RMQ就是维护静态区间极值问题,预处理的时间复杂度为O(n*logn),查询为O(1),对于 这道模板题,就必须是O(1)的输出。什么是倍增?倍增用到了2进制的思想。我们把数组分割为2的次方倍。