（沒有介紹標準算法的）RMQ問題

感謝杜哥代碼滋磁

//以下是廢話

RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

主要方法及复杂度如下：

1、朴素（即搜索），O(n)-O(qn) online。

2、线段树，O(n)-O(qlogn) online。

3、ST（实质是动态规划），O(nlogn)-O(q) online。

ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k<=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。

d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。

4、RMQ标准算法：先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ，O(n)-O(q) online。

首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。 ——來自百度百科

————————————————————————————————————廢話分割線———————————————————————————————————————————————————————

一·搜索

我懶得寫代碼，應該不太難就對了qwq

二·線段樹

我之前寫炸了的代碼忘記保存了，那麼就在這裡貼上杜哥的代碼好了emmm

這個維護的是區間最小值（廢話）還是很好懂的qwq

#include<iostream>

#include<cstdio>

#define maxn 1000010

#define INF 11000000

using namespace std;

int n, m;

int a[maxn];

#define lc i << 1

#define rc i << 1 | 1

int T[maxn * 4];

inline void maintain(int i){T[i] = min(T[lc], T[rc]);}

void build(int i, int l, int r){

    if(l == r){T[i] = a[l]; return ;}

    int m = l + r >> 1;

    build(lc, l, m); build(rc, m + 1, r);

    maintain(i);

}

void update(int i, int l, int r, int k, int v){

    if(l == r){T[i] = v; return ;}

    int m = l + r >> 1;

    if(k <= m) update(lc, l, m, k, v);

    else update(rc, m + 1, r, k, v);

    maintain(i);

}

int query(int i, int l, int r, int L, int R){

    if(l > R || r < L) return INF;

    if(L <= l && r <= R) return T[i];

    int m = l + r >> 1;

    return min(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));

}

inline void solve_1(){

    int x, y; scanf("%d%d", &x, &y);

    update(1, 1, n, x, y);

}

inline void solve_2(){

    int x, y; scanf("%d%d", &x, &y);

    printf("%d\n", query(1, 1, n, x, y));

}

int main(){

    scanf("%d", &n);

    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    build(1, 1, n);

    scanf("%d", &m);

    for(int i = 1; i <= m; ++i){

        int opt; scanf("%d", &opt);

        switch(opt){

        case 1 : solve_1(); break;

        case 0 : solve_2(); break;

        }

    }

    return 0;

}

三·ST表

看了百度百科才知道這竟然是動態規劃？！告辭.jpg

ST表有兩維，st[i][j]表示[j,j+2^i-1]的範圍內的最大（小）值。

如何維護？

首先我們可以確定，st[0][j]就是這個數本身，所以我們可以在此基礎上進行DP。二分的話顯然會快我們就二分好了qwq

於是很顯然，[j,j+2^i-1]可以分成區間[j,j+2^(i-1)-1]和[j+2^(i-1),j+2^i]，我們也就輕鬆地得到了狀態轉移方程：st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))])

一個小優化：提前預處理好[1,n]中每個數的log值（為什麼最大要到20呢？可能因為2^20足夠大吧qwq）

#include<cstdio>

#include<iostream>

using namespace std;

int Log[100005],st[23][100005],n,l,r,m;

inline int max(int a,int b){

	return a>b? a:b;

}

inline long long read(){

	long long a=0; int f=0; char p=getchar();

	while(!isdigit(p)) {f|=p=='-'; p=getchar();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48); p=getchar();}

	return f? -a:a;

}

int main()

{

	n=read(),m=read();

	for(int i=2;i<=n;++i) Log[i]=Log[(i>>1)]+1;

	for(int i=1;i<=n;++i)

		st[0][i]=read();

	for(int i=1;i<=20;++i)

		for(int j=1;j+(1<<i)-1<=n;++j)

			st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);

	while(m--){

		l=read(),r=read();

		int t=Log[r-l+1];

		printf("%d\n",max(st[t][l],st[t][r-(1<<t)+1]));

	}

	return 0;

}

四·標準算法

啥？這還有標準算法？笛卡爾樹？不認識不認識告辭了

巴特西

（沒有介紹標準算法的）RMQ問題

最新文章

热门文章