倍增 、RMQ、ST算法

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

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

第二行包含 N 个整数（记为 ai​），依次表示数列的第 i项。

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

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

输入

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

输出

9
9
7
7
9
8
7
9

分析：

可能被查询的子区间个数：

起点有n个，对于每个起点，其后每个点都可能是终点。

共有大约n^2个子区间，但全部查找最大值不现实，利用倍增思想 起点依旧是n个，但每个区间终点只取 从起点开始的 1、2、4、8、...个数的最后一个 ，终点logn个， 实现总区间个数为n*log(n)个，预处理这些区间的最大值。   

即需要预处理的区间个数为n*log(n) （预处理时间复杂度O(n*log(n))

预处理过程用到dp。

最后 O(1)查询。              查询区间总可以用两个预处理过的区间覆盖完全（但不会多出），区间重复不影响最大值求解。

代码：

#include 
#include 
#define maxn 100009
using namespace std;
int dp[maxn][100];     //dp[i][j]: 从i开始的2^j次幂个数的最大值
int main ()
{
    int n,t;
    scanf("%d%d",&n,&t);
    int i,j;
    for(i=1; i<=n; i++)
    {
        scanf("%d",&dp[i][0]);  //预处理dp数组
    }
    for(j=1; 1< 
(3条消息) 【白话系列】倍增算法_JarjingX-CSDN博客_倍增算法
 
//这个友链内容思想基本为本题大致思路，细品对本题理解很有帮助
 
//如有侵犯版权 友链作者可联系删除qaq