数列区间最大值
来源: 《信息学奥赛一本通》
算法标签 线段树
题目描述
输入一串数字,给你 M 个询问,每次询问就给你两个数字 X,Y,要求你说出 X 到 Y 这段区间内的最大数。
输入格式
第一行两个整数 N,M 表示数字的个数和要询问的次数;
接下来一行为 N 个数;
接下来 M 行,每行都有两个整数 X,Y。
输出格式
输出共 M 行,每行输出一个数。
数据范围
1≤N≤1E5,
1≤M≤1E6,
1≤X≤Y≤N,
数列中的数字均不超过231−1
输入样例:
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例:
5
8
思路
求区间最大,暴力是直接遍历o(n^2),但是数据上1E6,所以用线段树。
线段树
不管是查询还是更改看起来都好理解一点…
C++ 代码
#include<iostream>
#include<cstdio>
#include<climits>//包含INT_MIN
using namespace std;
const int N=1e5+10;
int w[N];//数值
struct Node
{
int l,r,maxv;
}tr[4*N];//二叉树 n+n/2+n/4..=2n 加底层最大 =4n
int pushup(int u)
{
return tr[u].maxv = max (tr[u<<1].maxv,tr[u<<1|1].maxv);//更新数据 两个子树当中取最大
}
void build(int u,int l,int r)//初始化线段树 u序号 lr具体范围
{
if(l==r)tr[u]={l,r,w[r]};//如果只有一个数据 即最大是当前数据
else
{
tr[u]={l,r};
int mid=l+r>>1;//初始化二叉树 只与结构有关 与本身数据无关 所以mid = l+r>>1
build(u<<1,l,mid),build(u<<1|1,mid+1,r);//递归找两个子树
pushup(u);//当前的最大值等于两个子树间的最大值
}
}
int query(int u,int l,int r)//u序号 lr要查找的范围
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].maxv;//如果要查找的范围包含当前范围则直接返回最值
else
{
int maxv=0;
int mid=tr[u].l+tr[u].r>>1;//与本身数据有关 做中间值 用于找包含部分
if(l<=mid)maxv=query(u<<1,l,r);//如果左边有包含部分 则更新左子树
if(r>=mid+1)maxv=max(maxv,query(u<<1|1,l,r));//如果右边有包含部分 则更新右子树
return maxv;//当前maxv实际是由底层逐层比对返回的在指定区域内的最大值
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
build(1,1,n);//初始化线段树
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(1,x,y));
}
return 0;
}