【題目鏈接】

ybt 1541：【例 1】數(shù)列區(qū)間最大值

【題目考點(diǎn)】

1. RMQ問題

RMQ問題是給定一個(gè)序列，多次求區(qū)間最值的問題。
常用解法：

• ST表：離線算法，預(yù)處理$O(n\log n)$，區(qū)間查詢$O(1)$
• 線段樹：在線算法，預(yù)處理$O(n)$，區(qū)間查詢$O(\log n)$

【解題思路】

解法1：ST表

概念及解析見洛谷 P3865 【模板】ST 表 && RMQ 問題

解法2：線段樹

基本概念及解析見洛谷 P3374 【模板】樹狀數(shù)組 1（線段樹解法）
線段樹中每個(gè)結(jié)點(diǎn)保存的值為該結(jié)點(diǎn)表示的區(qū)間中的最大值。
使用孩子結(jié)點(diǎn)的值更新雙親結(jié)點(diǎn)的值時(shí)（pushUp操作），取左右孩子結(jié)點(diǎn)的值的最大值，即為當(dāng)前結(jié)點(diǎn)的值。
區(qū)間查詢時(shí)：

• 如果當(dāng)前結(jié)點(diǎn)表示的區(qū)間被待查詢區(qū)間完全包含，則返回當(dāng)前結(jié)點(diǎn)的值。
• 如果當(dāng)前結(jié)點(diǎn)表示的區(qū)間沒有被待查詢區(qū)間包含，則求出左右孩子結(jié)點(diǎn)表示的區(qū)間在待查詢區(qū)間中的最大值，返回這兩個(gè)值的最大值。

【題解代碼】

解法1：ST表

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define L 30
int a[N], lg[N], f[N][L];//f[i][j]：a[i]~a[i+2^j-1]中的最大值 
void initLg(int n)
{for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;
}
int query(int l, int r)
{int k = lg[r-l+1];return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;initLg(n);for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i)f[i][0] = a[i];for(int j = 1; j <= lg[n]; ++j)for(int i = 1; i+(1<<j)-1 <= n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);while(m--){cin >> l >> r;cout << query(l, r) << '\n';}return 0;
}

解法2：線段樹

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int l, r, val;
} tree[4*N];
int a[N];
void pushUp(int i)
{tree[i].val = max(tree[2*i].val, tree[2*i+1].val);
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r;if(l == r){tree[i].val = a[l];return;}int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);pushUp(i);
}
int query(int i, int l, int r)
{if(tree[i].l > r || tree[i].r < l)return INT_MIN;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return max(query(2*i, l, r), query(2*i+1, l, r));
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];build(1, 1, n);while(m--){cin >> l >> r;cout << query(1, l, r) << '\n';}return 0;
}