信息学奥赛一本通 1541：【例 1】数列区间最大值

【题目链接】

ybt 1541：【例 1】数列区间最大值

【题目考点】

1. RMQ问题

RMQ问题是给定一个序列，多次求区间最值的问题。
常用解法：

• ST表：离线算法，预处理$O(n\log n)$，区间查询$O(1)$
• 线段树：在线算法，预处理$O(n)$，区间查询$O(\log n)$

【解题思路】

解法1：ST表

概念及解析见洛谷 P3865 【模板】ST 表 && RMQ 问题

解法2：线段树

基本概念及解析见洛谷 P3374 【模板】树状数组 1（线段树解法）
线段树中每个结点保存的值为该结点表示的区间中的最大值。
使用孩子结点的值更新双亲结点的值时（pushUp操作），取左右孩子结点的值的最大值，即为当前结点的值。
区间查询时：

• 如果当前结点表示的区间被待查询区间完全包含，则返回当前结点的值。
• 如果当前结点表示的区间没有被待查询区间包含，则求出左右孩子结点表示的区间在待查询区间中的最大值，返回这两个值的最大值。

【题解代码】

解法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;
}