区间最值问题RMQ,学习整理

#include <cstdio>#include <algorithm>using namespace std;///////////////////////////////const int MAX_N = 5e4 + 5;const int INF = 0x3f3f3f3f;typedef pair<int, int> P;///////////////////////////////P dat[4 * MAX_N];//存储线段树的全局数组int n;//////初始化void init { n = 1; while  n <<= 1;//简单起见,把元素个数扩大到2的幂 for (int i = 0; i < 2 * n - 1; ++i) { dat[i].first = INF;//存储区间最小值 dat[i].second = -INF;//存储区间最大值 }}//把第k个值更新为xvoid update(int k, int x) { k += n - 1; dat[k] = P; while  {//向上更新 k =  / 2; dat[k].first = min(dat[2 * k + 1].first, dat[2 * k + 2].first); dat[k].second = max(dat[2 * k + 1].second, dat[2 * k + 2].second); }}//////////////////查询P query(int a, int b, int k, int l, int r) {//k是节点编号 if (a <= l && r <= b) return dat[k]; if (a > r || b < l) return P(INF, -INF); P vl = query(a, b, 2 * k + 1, l,  / 2); P vr = query(a, b, 2 * k + 2,  / 2 + 1, r); return P(min(vl.first, vr.first), max(vl.second, vr.second));}int main() { int N, Q; scanf("%d%d", &N, &Q); init; for (int i = 0; i < N; ++i) { int x; scanf("%d", &x); update; } for (int i = 0; i < Q; ++i) { int a, b; scanf("%d%d", &a, &b); P p = query(a - 1, b - 1, 0, 0, n - 1); printf("%dn", p.second - p.first); } return 0;}

(二)然后是查询。

解题方法:用线段树和疏落表均能够做。

void RMQ(int num) //预处理->O(nlogn)  
{  
    for(int j = 1; j < 20; ++j)  
        for(int i = 1; i <= num; ++i)  
            if(i + (1 << j) - 1 <= num)  
            {  
                maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);  
                minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);  
            }  
} 
  • 稀疏表本质为动态规划。

A数列为:3 2 4
5 6 8 1 2 9 7

Sparse Table
算法能够在O的预管理现在实现O的询问作用,进而化解了数居多的RMQ难题。基于ST的RMQ在预管理时的大运复杂度和空间复杂度都落得了O,与线段树的RMQ比较,不能飞速地对值进行翻新。参照他事他说加以考察资料:

例如表达,要求区间[2,8]的最大值,k
= log2(8 – 2 + 1)= 2,即求max(F[2, 2],F[8 – 2 ^ 2 + 1, 2]) =
max(F[2, 2],F[5, 2]);

  • 线段树

(一)首先是预处理,用动态规划(DP)消除。

N(1 ≤ N ≤ 50000), Q(1 ≤ Q ≤ 300000);N为数字个数,1 ≤每种数 ≤
1,000,000。。。如:输入:6 31734251 54 62 2出口:630

答案是:4
* 2 * 2 = 16。所以大家要写成5 – (1 << 2)才是5-1 * 2 * 2 =
1。

#include <cstdio>#include <algorithm>#include <cmath>using namespace std;//////////////////////////const int INF = 0x3f3f3f3f;const int MAX_N = 5e4 + 5;typedef pair<int, int> P;/////////////////////////////int num[MAX_N];P dp[MAX_N][20];void init { int k =  / log; for (int i = 0; i < n; ++i) for (int j = 0; j <= k; ++j) { dp[i][j].first = INF; dp[i][j].second = -INF; } }void creat { for (int i = 0; i < n; ++i) dp[i][0].first = dp[i][0].second = num[i]; int k =  / log; for (int j = 1; j <= k; ++j) for (int i = 0; i + (1 << j) - 1 < n; ++i) { dp[i][j].first = min(dp[i][j - 1].first, dp[i + (1 << ][j - 1].first); dp[i][j].second = max(dp[i][j - 1].second, dp[i + (1 << ][j - 1].second); }}P query(int s, int e) { int k = (log(e - s + 1) / log; return P(min(dp[s][k].first, dp[e - (1 << k) + 1][k].first), max(dp[s][k].second, dp[e - (1 << k) + 1][k].second));}int main() { int N, Q; scanf("%d%d", &N, &Q); for (int i = 0; i < N; ++i) scanf("%d", &num[i]); init; creat; for (int i = 0; i < Q; ++i) { int a, b; scanf("%d%d", &a, &b); P p = query(a - 1, b - 1); printf("%dn", p.second - p.first); } return 0;}

RMQ(Range
Minimum/马克西姆um
Query),即距离最值查询,是指那样一个难题:对于长度为n的数列A,回答若干叩问RMQ(A,i,j)(i,j<=n),重回数列A中下标在i,j之间的小小/大值。那八个难题是在事实上行使中常常遇到的主题素材,上面介绍一下消除那二种问题的可比赶快的算法。当然,该难题也能够用线段树(也叫区间树)消除,算法复杂度为:O(N)~O(logN),这里我们暂不介绍。

n个成分的线段树的最先化的小运复杂度和空间复杂度都以O,对于n个成分,每贰次操作的复杂度是O。

因为这些区间的长短为j

难题大要:给出一串数字,然后交由贰个区间a
b,输出从a到b的最大的数和微小的数的差。


预处理:
预管理是应用dp的思念,用f[i][j]表示区间[i,i+2j-1]中的最大值(即从i发轫,长度为2j的闭区间)。开端时,f[i][0]
就是距离[i][i]的值,即f[i][0] =
num[i],好了,最初值找到了,上面是状态转移方程:f[i][j] = max
(f[i][j-1],f[i+2][j-1])。即把[i,i+2j-1]区间分为[i,i+2-1]和[j+2,j+2+2-1]多少个等长短的区间(区间长度都以2^,有了起首值和情形转移方程,我们可以自底向上递推出具备的f[i][j]的值。边界值的管理:
由于距离最大尺寸为n,所以二维边界最大值为log/log;一维边界为i+2^j-1<=n。查询
要是要询问区间[a,b]的最大值,由于距离的尺寸很恐怕不是2的整数幂,所以我们要把区间划分为长度为2的卡尺头幂的两有的,並且那三个的并集必需是[a,b]。为了兑现那个方案,大家需求先求出多少个最大k,使得2k<=,那样就足以把区间分为两片段[a,a+2k-1]和[b-2^k+1,b],使它们既可以不抢先[a,b]区间的范围,又能把区间全体掩盖。于是,[a,b]区间的最大值就十二分上述多个区间的最大值中最大的丰硕。


 
下边是DP预管理的代码实现:

 

此处大家须求在意的是循环的顺序,大家发掘外层是j,内层所i,那是干什么吗?能够是i在外,j在内啊?

对此该难题,最轻便想到的减轻方案是遍历,复杂度是O(n)。但当数据量相当大且查询很频仍时,该算法无法在使得的时光内查询出正解。

例如:

处境转移方程的含义是:我们先得到F[i,0](即1个成分)的值,然后通过2个1个因素的最值,得到全体长度为F[i,1](即2个要素的最值),然后再通过2个2个要素的最值,得到全秘书长度为F[i,2](即4个成分的最值),以此类推更新具有长度的最值。

与此同有时间大家得以轻便的收看F[i,0]就等于A[i]。(DP的开端值)

在这边大家也亟需小心八个地方,就是<<运算符和+-运算符的事先级。

发表评论

电子邮件地址不会被公开。 必填项已用*标注