给定一个长度为 N N 的数列，和 M M 次询问，求出每一次询问的区间内数字的最大值。
<!--more-->
## 题目链接
[Lougu-3865-【模板】ST表](https://www.luogu.org/problem/P3865)
## 输入输出格式
### 输入格式：
第一行包含两个整数 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的次方倍。
Lougu-3865-【模板】ST表（倍增写法）