做招聘网站的风投,做网站美工,工商企业查询,icp查询官网版权声明#xff1a;本文为博主原创文章#xff0c;遵循 CC 4.0 BY-SA 版权协议#xff0c;转载请附上原文出处链接和本声明。 本文链接#xff1a;https://blog.csdn.net/qq_41311604/article/details/79900893 /div!--一个博主专栏付费入口--!--一个… 版权声明本文为博主原创文章遵循 CC 4.0 BY-SA 版权协议转载请附上原文出处链接和本声明。 本文链接https://blog.csdn.net/qq_41311604/article/details/79900893 /div!--一个博主专栏付费入口--!--一个博主专栏付费入口结束--link relstylesheet hrefhttps://csdnimg.cn/release/phoenix/template/css/ck_htmledit_views-4a3473df85.csslink relstylesheet hrefhttps://csdnimg.cn/release/phoenix/template/css/ck_htmledit_views-4a3473df85.cssdiv classhtmledit_views idcontent_viewsp现在给你一个问题给你一个数组 其中有N个数字现在给你一次询问给你区间[l r]问你在这个区间内的最大值为多少?/p哇这题简单啊一个for循环遍历数组记录最大值输出即可啊。 那好现在我告诉你假设N为50000给你Q次询问(1 ≤ Q ≤ 200,000),如果这种情况我们还每次都进行暴力遍历求解的话那么无论你提交几万次都会得到如下结果: 是的这种暴力遍历求解虽然思维简单代码简短但是很慢啊。 那该怎么做呢以前我也不会啊自从学了RMQ诶真好用我们全家都用它 RMQRange Minimum/Maximum Query即区间最值查询。RMQ算法一般用较长时间做预处理时间复杂度为O(nlogn)然后可以在O1的时间内处理每次查询。 下面我们从一个实际问题来解释RMQ
我们假设数组arr为1268437
我们设二维数组dp[i][j]表示从第i位开始连续 个数中的最小值。例如dp[2][1]就表示从第二位数开始连续两个数的最小值也就是从第二位数到第三位数的最小值即26中的最小值所以dp[2][1] 2; 其实我们求 dp[i][j] 的时候可以把它分成两部分第一部分是从 到 第二部分从到 为什么可以这么分呢其实我们都知道二进制数前一个数是后一个的两倍那么可以把 到 这个区间通过分成相等的两部分 那么转移方程很容易就写出来了。dp[i][0]就表示第i个数字本身 dp[i][j] min(dp [i][j - 1], dp [i (1 j - 1)][j - 1])
由此给出下列代码
void rmq_init(){ for(int i1;iN;i)dp[i][0]arr[i];//初始化 for(int j1;(1j)N;j) for(int i1;i(1j)-1N;i)dp[i][j]min(dp[i][j-1],dp[i(1j-1)][j-1]);}
这里需要注意一个循环变量的顺序我们看到外层循环变量为j内层循环变量为i这是为什么呢可以互换一下位置吗 答案当然是不可以我们要理解这个状态转移方程的意义这个状态方程的含义是先更新每两个元素中的最小值然后通过每两个元素的最小值获得每4个元素中的最小值依次类推更新所有长度的最小值。 而如果是i在外j在内的话我们更新的顺序就变成了从1开始的前1个元素前2个元素前4个元素前8个元素。。。
当j等于3的时候dp[1][3] min(min(ans[0],ans[1],ans[2],ans[3]),min(ans[4],ans[5],ans[6],ans[7])))的值
但是我们根本没有计算min(ans[0],ans[1],ans[2],ans[3])和min(ans[4],ans[5],ans[6],ans[7])所以这样的方法肯定是错误的。
为了避免这样的错误一定要好好理解这个状态转移方程所代表的含义。 接下来我们来讲解RMQ的查询部分假设我们需要查询区间[l r]中的最小值令k 则区间[l, r]的最小值RMQ[l,r] min(dp[l][k], dp[r - (1 k) 1][k]); 但是为什么这样就可以保证是区间最小值了呢 dp[l][k]维护的是区间 [l, l 2^k - 1] , dp[r - (1 k) 1][k]维护的是区间 [r - 2^k 1, r] 。
那么只要我们保证 ≤ 就能保证RMQ[l,r] min(dp[l][k], dp[r - (1 k) 1][k]) 接下来我们用分析法来证明这个不等式
我们假设 ≤ 这个等式成立
即有 r - l 2 ≤ 也就是 r - l 2 ≤
又因为 k ;
那么 r - l 2 ≤ 2 * (r - l 1)
则 r - l 2 ≤ 2*(r - l) 2
即 r - l ≤ 2*(r-l)
所以 r - l ≥ 0即假设成立
我们举个例子 l 4r 6;
假设数组arr为1268437
此时 k 1
则区间[4,6]的最小值 mindp[4][1],dp[5][1]
dp[4][1] 4dp[5][1] 3所以区间[4,6]的最小值 min(dp[4][1],dp[5][1]) 3
我们很容易看出来答案是正确的。
由此给出查询部分代码
int rmq(int l,int r){ int klog2(r-l1); return min(dp[l][k],dp[r-(1k)1][k]);}
好了至此RMQ全部介绍完毕。
