RMQ 区间最大值 最小值查询

时间:2020-11-26 15:15:18
/*RMQ  更新最小值操作  By:draymonder*/

#include
<iostream>
#include
<cstdio>

using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1 << 17;
const int INF = 0x3f3f3f3f;
typedef
long long LL;

int n,s[2*maxn-1];

void init(int a)//把元素个数扩充到2的幂 简便
{
n
= 1;
while (n < a)
n
*=2;
for(int i=0;i<2*n-1;i++)
s[i]
= INF; //把所有的值 都变成INF

}

void update(int k,int a)//把第k个值更新为a
{
k
+= n-1;
s[k]
= a;//找到 只是k的这个区间的位置 然后依次更新
while (k > 0)
{
k
= ( k - 1 )/2;
s[k]
= min(s[k*2+1],s[k*2+2]);
}
}
//求[a,b)的最小值
//后面的参数是为了计算起来方便而传入的
//k是节点的编号,l,r表示这个节点对应的[l,r)区间
//在外部调用的时候用query(a,b,0,0,n)

int query(int a,int b,int k,int l,int r)
{
if(r <= a || b <= l) return INF;//[a,b) 与 [l,r)不相交
//如果 [a,b)完全包含[l,r) 直接返回当前k节点的值
if(a <= l && r<= b) return s[k];
else {
//否则返回两个儿子中值较小者
int v1 = query(a,b,k*2+1, l , (l+r)/2);
int v2 = query(a,b,k*2+1,(l+r)/2 , r);
return min(v1,v2);
}

}