关键词：
没用的话：好像好久没更博了，无聊就讲讲算法吧（主要找不到水题）。
感觉针对初学者，老师教这个算法时没怎么懂，最近（大概1、2个月前吧）老师又教了lca（最近公共祖先，额，可以百度，我就不讲了，可能以后会再写一篇博客关于这个）讲到lca转RMQ才又回来认真复（xue）习（xi）。大概搞懂了，本质是dp。
认识RMQ：
要学习RMQ，首先要知道RMQ求什么吧？
RMQ简单来说就是求区间的最大值（最小值）。
什么？没懂！
举个栗子：
1 -2 9 10 15 38 -9
这里有 7 个数（随便输的），RMQ就是用来查询这些数中的最大值（最小值），但是是区间的。比如查询 [1,3] 这个区间的最大值 就是 9 这个值 .
这样讲应该懂了吧。
暴力解法：
其实这样的题目可以直接暴力对吧，一重循环枚举区间就好了。
但是如果有多个询问效率显然就低了很多，因为可能会重复计算。
所以会有人想到dp吧。
RMQ解法：
而RMQ算法就是一个神奇dp。
RMQ感觉很少用到，但这个dp思想却能有很大启发！
进入正题——RMQ（以下以求最大值为例）
F[i,j]表示 从 i 开始 到i+2j（可能不是很清楚，是二的 j 次方）这个区间中的最大值
什么？为什么要用 2j 这么奇怪的东西？ 这就是RMQ的神奇
然后就是初始值了 显然 F[i,0]=a[i](原始数组) 对吧 因为 20 等于1 一个数的区间最大值肯定就是这个数 你总不会说 [2,2] 这个区间的最大值在[3,3]这个区间吧?
辣么状态转移方程呢？
F[i,j]=max(f[i,j-1],f[i+2j-1,j-1])
这么啪给你肯定是不懂的
自己画了张图：
假如要求绿色这段区间的最大值，实际上主要这段蓝色这段区间的最大值和红色这段区间的最大值就可以了对吧，
绿色这段区间的最大值就会等于max（蓝色最大值，红色最大值）
因为dp是递推而来的，所以蓝色最大值和红色最大值是已知的，
所以方程就是 F[i,j](这里指[1,4]这个区间，所以i=1,j=2)=max（f[i,j-1](指[1,2]这个区间，所以i=1,j=1) ，f[i+2j-1,j-1](指[3,4]这个区间，所以i=1+21=3 j=1)）
可能不好理解，j可以抽象为[1,4] 4个数， j-1 就为2个数 ，已知 2 个连续的 2个数的区间 那么就能求出1个 4个数的区间
大概代码：
for i=1 --> n f[i,0]=a[i]; //初始化 for j=1 --> log2(n) for i=1 --> n f[i,j]=max(f[i,j-1],f[i+(1 << (j-1))]);// RMQ状态转移方程
如果你问为什么j放外循环，那就是对RMQ还不够理解。
如果j放了内循环，那么求解顺序就变成了 f[1..n,1]...f[1..n,log(n)] 这样就不会先求出 2 个连续的 2个数的区间的最大值，也就不能dp了。
大概就讲这么多，希望有帮助。
RMQ应用还是不多，也就这是lca ，建议学的是思路.
预留 lca 网址位：（有时间写篇lca）
rmq算法（st算法）
...的时候，这样的暴力就无法进行了。这时我们可以通过RMQ算法来解决这个问题。RMQ(ST)：（关于学习RMQ的博 查看详情
rmq算法
...后看了篇博客，发现其在求最小的字典序的时候用到了RMQ算法。问徐大佬这是个什么东西，大佬说：你们肯定学过，这个东西1个月以前60级的就问过我了。为了不让学弟学妹落下，我决定还是学学RMQ算法吧。。one 前言RMQ（Ran... 查看详情
hiho16rmq-st算法rmq-st算法(代码片段)
传送门：RMQ-ST算法RMQ(RangeMinimum/MaximumQuery)区间范围最值查询问题题意求指定区间值最小的元素思路其实就是二分法的思路，统计所有长度为2的非负整数次幂的区间。然后将所求转化到在包含的几个区间之中寻找最小值。OnlineACCod... 查看详情
rmq算法
...遇到的问题，下面介绍一下解决这两种问题的比较高效的算法。当然，该问题也可以用线段树（也叫区间树）解决，算法复杂度为：O(N)~O(logN)，这里我 查看详情
rmq算法入门
...遇到的问题。以下介绍一下解决这两种问题的比較高效的算法。当然，该问题也能够用线段树（也叫区间树）解决，算法复杂度为：O(N)~O(logN)，这里我 查看详情
rmq问题之st算法
RMQ问题之ST算法RMQ(RangeMinimum/MaximumQuery)问题，即区间最值问题。给你n个数，a1,a2,a3,...,an，求出区间[l,r]的最大值。举例：a={1,2,3,4,5,6,7,8,9},求出区间[4,8]中的最值。（答案：8)这个问题最朴素的想法是用一个循环每次比较大小，但... 查看详情
lca上的rmq模板算法
Howfaraway？TimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):10764 AcceptedSubmission(s):3923ProblemDescriptionTh 查看详情
rmq入门
...最小值，我们自然而然就想到了一个O（n）时间复杂度的算法，但是如果询问有很多呢？这样必然超时。当然我们可以用线段树来解，使得每一次查询的时间降到log(n)，但是对于RMQ算法，只要我们做了些预处理，之后的查询我们... 查看详情
rmq算法(代码片段)
定义RMQ(RangeMinimum/MaximumQuery)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。简介主要方法及复杂度如下：1、朴素（即搜索），O... 查看详情
rmq的st算法
·RMQ的ST算法 状态设计： F[i,j]表示从第i个数起连续2^j个数中的最大值 状态转移方程（二进制思想）： F[i,j]=max（F[i，j-1],F[i+2^ 查看详情
rmq问题st算法(代码片段)
...某个区间的最大值或最小值的问题，主要求解方法之一ST算法；ST算法其实是倍增思想的产物,等下看代码实现就很明显了ST算法通常用在要多次询问一些区间的最值的问题中，相比于线段树，它的程序实现更简单，运行速度更快;S... 查看详情
hdu2586+hdu4123(rmq算法与lca）
转自：http://blog.csdn.net/liang5630/article/details/7917702rmq算法可用来求区间最值，区间最值差，树上最近公共祖先，时间复杂度O（nlogn）1.概述RMQ（RangeMinimum/MaximumQuery），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回... 查看详情
笔记：rmq（区间最值）之st算法
RMQ（区间最值）之ST算法 RMQ即RangeMinimum/MaximunQuery中文意思：查询一个区间的最小值/最大值比如有这样一个数组：A{3245681297}，然后问你若干问题：数组A下标2~7区间最小的值是多少？ 最小值是（1）... 查看详情
动态规划-rmq问题（st算法）(代码片段)
文章目录RMQ问题ST算法模板例题P2251质量检测P1816忠诚P2216[HAOI2007]理想的正方形RMQ问题RMQ（RangeMinimum/MaximumQuery）问题，是求区间最大值或最小值，即范围最值问题。暴力解法是对每个询问区间循环求解，设区间... 查看详情
rmq算法模板
分别写了下标从0和1开始的两种 1#include<stdio.h>2#include<string.h>3#include<algorithm>4#include<math.h>5usingnamespacestd;67constintmaxn=1e5+5;8constintmaxl=20;910intma[maxn][maxl];11i 查看详情
基于dp+位运算的rmq算法(代码片段)
来源：http://blog.csdn.net/y990041769/article/details/38405063RMQ算法，是一个快速求区间最值的离线算法，预处理时间复杂度O（n*log(n)），查询O(1)，所以是一个很快速的算法，当然这个问题用线段树同样能够解决。 问题：给出n个数ai，... 查看详情
rmq
...angeMinimum/MaximumQuery）即区间最大最小值问题。有一个离线算法（ST算法），这个算法是很高效了，时间是O（nlogn）：（用O（nlogn）的时间进行预处理，再用O（1）的时间进行区间查询）1.先是预处理（用动态规划解决） A数列为... 查看详情
倍增rmq的st表算法
...区间最大值为例）ST表：一种利用dp求解区间最值的倍增算法。定义：f[i][j]表示i到i+2^j-1这段区间的最大值。预处理：f[i][0]=a[i]。即i到i区间的最大值就是a[i]。状态转移：将f[i][j]平均分成两 查看详情