[Acwing] (RMQ) 算法总结|例题分析

RMQ(ST表|跳表) 优点:

快,很容易写

缺点:

不能改

思路:

倍增+动态规划

f[i,j]表示 从i开始长度是 i^j 的区间中最大值是多少

没错右下角是y总

如何查询区间呢

code:

#include 
#include 
#include 
#include 

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

void init()
{
    for (int j = 0; j