RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列a，回答若干询问RMQ（A,i,j）(i, j&=n)，返回数列a中下标在i，j之间的最小/大值。如果只有一次询问，那样只有一遍for就可以搞定，但是如果有许多次询问就无法在很快的时间处理出来。在这里介绍一个在线算法。所谓在线算法，是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理，待信息充足以后便可以用较少的时间回答每个查询。ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。
步骤如下：
假设a数组为：
1， 3， 6， 7， 4， 2， 5
1.首先做预处理（以处理区间最小值为例）
设mn[i][j]表示从第i位开始连续2^j个数中的最小值。例如mn[2][1]为第2位数开始连续2个的数的最小值，即3, 6之间的最小值，即mn[2][1] = 3;
之后我们很容想到递推方程：
mn[i][j] = min(mn[i][j - 1], mn[i + (1 && j - 1)][j - 1])
附上伪代码：
for(int j = 0; j & 20; j ++)
for(int i = 1; i + (1 && j) &= n + 1; i ++)
mn[i][j] = min(mn[i][j - 1], mn[i + (1 && (j - 1))][j - 1]);
咦？为什么第二行是i + （1 && j) &= n + 1呢？因为mn[i][j]表示连续2^j个数，所以mn[i][j]所维护的区间为[i, i + (1 && j) - 1],所以在最后要+1，其实是为了方便，写成i + (1 && j) - 1 &= n感觉左边太长了，所以写在右边了。
那么为什么j要写在外围？如果写在里面的输出结果是这样的
我们会发现没有更新过，这是为什么呢？&因为我们在更新的时候是通过要通过2^(j - 1)的区间来更新2^j的区间，来看状态转移方程：
mn[i][j] = min(mn[i][j - 1], mn[i + (1 && j - 1)][j - 1])
我们发现如果j写在里面的话，在更新mn[i][j]的时候会发现mn[i +(1&&j - 1)][j - 1]还没有更新，所以才会出现这样的结果，正确结果如下：
咦？为什么还有0？我们来看伪代码：
for(int j = 0; j & 20; j ++)
for(int i = 1; i + (1 && j) &= n + 1; i ++)
mn[i][j] = min(mn[i][j - 1], mn[i + (1 && (j - 1))][j - 1]);
看第二行会发现，对于i + （1 &&& j) - 1超过n的，我们没有更新，如图中的mn[5][2]，5 + 2^2 - 1 = 8 & 7所以没有更新，但这并不影响询问的结果。
假设我们需要查询区间[l, r]中的最小值，令k = log2(r - l + 1); 则区间[l, r]的最小值RMQ[l,r] = min(mn[l][k], mn[r - (1 && k) + 1][k]);
那么为什么这样就可以保证为区间最值吗?
mn[l][k]维护的是[l, l + 2 ^ k - 1], mn[r - (1 && k) + 1][k]维护的是[r - 2 ^ k + 1, r] 。
那么我们只要保证r - 2 ^ k + 1 &= l + 2 ^ k - 1就能保证RMQ[l,r] = min(mn[l][k], mn[r - (1 && k) + 1][k])；
我们用分析法来证明下：
若r - 2 ^ k + 1 &= l + 2 ^ k - 1;
则r - l + 2 &= 2 ^ (k + 1);
又因为&k = log2(r - l + 1)；
则r - l + 2 &= 2 *(r - l + 1);
则r - l &= 0;
显然可得。
由此得证。
我们来举个例子 l = 4, r = 6;
此时k = log2(r - l + 1) = log2(3) = 1;
所以RMQ[4, 6] = min(mn[4][1], mn[5][1]);
mn[4][1] = 4, mn[5][1] = 2;
所以RMQ[4, 6] = min(mn[4][1], mn[5][1]) = 2;
我们很容易看出来了答案是正确的。
附上总代码：（以结构体的形式写出）：
1 #include &cstdio&
2 #include &algorithm&
3 using namespace
4 const int N = 100000 + 5;
6 int a[N];
8 int mn[N][25];
10 int n, q, l,
12 struct RMQ{
int log2[N];
void init(){
for(int i = 0; i &= i ++)log2[i] = (i == 0 ? -1 : log2[i && 1] + 1);
for(int j = 1; j & 20; j ++)
for(int i = 1; i + (1 && j) &= n + 1; i ++)
mn[i][j] = min(mn[i][j - 1], mn[i + (1 && j - 1)][j - 1]);
int query(int ql, int qr){
int k = log2[qr - ql + 1];
return min(mn[ql][k], mn[qr - (1 && k) + 1][k]);
26 void work(){
rmq.init();
scanf("%d", &q);
while(q --){
scanf("%d%d", &l, &r);
printf("%d\n", rmq.query(l, r));
35 int main(){
while(scanf("%d", &n) == 1){
for(int i = 1; i &= i ++)scanf("%d", a + i), mn[i][0] = a[i];
&参考论文：
阅读(...) 评论()RMQ--ST表算法理解
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j&=n)，返回数列A中下标在i，j之间的最小/大值。
ST算法（Sparse Table），ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法，它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。
以求最小值为例，设dp [ i, j ]表示[ i, i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最小值时答案就是min(dp[a,k], dp[b-2^k+1,k])，其中 k 是满足2^k&=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。
注释: [a, a+(1&&k)-1] ~[b-2^k+1,b-2^k+1+2^k-1 ]
得到b-2^k+1&=a （=&
k&=[ln(b-a+1)/ln(2)] ）（当且取等号时k最大）（k取到最大，能保证覆盖待求最值的区间）
那么如何求出dp[ i ][ j ]呢？
（一）首先是预处理，用动态规划（DP）解决。
设A[i]是要求区间最值的数列，dp [i, j]表示从第i个数起连续2^j个数中的最小值。（DP的状态）
A数列为：3 2 4 5 6 8 1 2 9 7
dp [1，0]表示第1个数起，长度为2^0=1的最小值，其实就是3这个数，然后F [ 2, 0 ]=2……
同理 dp[1,1] = min(3,2) = 2, dp[1，2]=min(3,2,4,5) = 2，dp [1，3] = min(3,2,4,5,6,8,1,2) = 1
并且我们可以容易的看出dp[i,0]就等于A[i]。（DP的初始值）
这样，DP的状态、初值都已经有了，剩下的就是状态转移方程。
我们把dp [i，j]平均分成两段（因为dp [ i，j ]一定是偶数个数字）。
从 i 到i + 2 ^ (j - 1) - 1为一段，i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。dp [i，j]就是这两段各自最小值中的最小值。于是我们得到了状态转移方程dp[i, j]=min（dp[i，j-1],dp[i
+ 2^(j-1)，j-1]）。
void rmp_st(int n)
//预处理ST表,数组中共n个元素
for(int i=1;i&=n;i++)
dp[i][0]=A[i];
int m=(int)(log((double)n)/log(2.0)));
//【i，i+2^j-1】2^j&= n（区间长度） j&=log n/ log2;
//或者上步骤省略直接写成for(j=1;(2&&j)&=n;j++) ……
for(int j=1;j&=m;j++)
for(int i=1;i+(1&&j)-1&=n;i++)
dp[i][j]=min(dp[i][j-1],dp[i+(1&&j)][j-1]);
//预处理得到的dp[i][j]表示 从第i位到第i+2^j-1位当中最小的值
&/span&这里我们需要注意的是循环的顺序，我们发现外层是j，内层所i，这是为什么呢？可以是i在外，j在内吗？
答案是不可以。因为我们需要理解这个状态转移方程的意义。
状态转移方程的含义是：先更新所有长度为dp [ i,0 ] 即1个元素，然后通过2个1个元素的最值，获得所有长度为dp [i,1]即2个元素的最值，然后再通过2个2个元素的最值，获得所有长度为dp [i,2]即4个元素的最值，以此类推更新所有长度的最值。而如果是i在外，j在内的话，我们更新的顺序就是dp [1,0],dp [1,1],dp [1,2],dp [1,3],表示更新从1开始1个元素，2个元素，4个元素，8个元素(A[0],A[1],....A[7]）的最值，这里
dp[1,3]=min(min(A[0],A[1],A[2],A[3]),min(A[4],A[5],A[6],A[7]))的值，但是我们根本没有计算min(A[0],A[1],A[2],A[3])和min(A[4],A[5],A[6],A[7])，所以这样的方法肯定是错误的。
为了避免这样的错误，一定要好好理解这个状态转移方程所代表的含义。
（二）然后是查询。
假如我们需要查询的区间为( i,j )，那么我们需要找到覆盖这个闭区间(左边界取i，右边界取j)的最小幂（可以重复，比如查询5，6，7，8，9，我们可以查询）。
因为这个区间的长度为j - i + 1,所以我们可以取k=log2( j - i + 1)（k取到最大）。
则有：RMQ(A, i, j)=min{ dp [i , k], dp [ j - 2 ^ k + 1, k]}。
举例说明，要求区间[2，8]的最大值，k = log2（8 - 2 + 1）= 2，即求min (dp [2, 2]，dp [8 - 2 ^ 2 + 1, 2]) = min (dp [2, 2]，F[5, 2])；
在这里我们也需要注意一个地方，就是&&运算符和+-运算符的优先级。
比如这个表达式：5 - 1 && 2是多少？
答案是：4 * 2 * 2 = 16。所以我们要写成5 - (1 && 2)才是5-1 * 2 * 2 = 1。
int rmp_find(int l,int r)
//求区间 l 到 r 之间的最值
int k=(int)(log(double(r-l+1))/log(2.0));
return min(dp[l][k],dp[r-(1&&k)+1][k])
没有更多推荐了，当前位置: &&>> 阅读正文
View: 25,564
Author: Dong
- 359,966 阅 - 273,614 阅 - 261,861 阅 - 247,109 阅 - 245,229 阅 - 243,153 阅 - 223,097 阅 - 214,591 阅 - 211,833 阅 - 204,386 阅
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = '
collapsItems['collapsArch-'] = 'The newest version can be found
RMQ 问题，即区间最值查询，是在长度为 N 的序列中求出其连续的子序列中最大/最小值的问题。
ST 算法适用于解决 RMQ 问题，是一个较长时间预处理，（时间复杂度为 O(NlogN)），在 O(1) 的时间内回答每个查询的算法。
算法思想及类型
算法思想为人人为我 我为人人，本质为动态规划。
实现顺序为：
区间大小为单位大小，计算出每个单位中最大/最小值（即为本身）
逐渐增大区间大小（每次乘二），利用其两个子连续区间动态规划出这次计算的区间的最大/最小值
这里M[i][j]的最值即为[i,i+1-(2^j)]的最值，也就是[i,i+1-(2^(j-1))]的最值和[i+(2^(j-1)),i+1-(2^j)]最值的max/min，所以可以这么DP
void process2(int M[MAXN][LOGMAXN], int A[MAXN], int N) {
// initialize M for the intervals with length 1
// 将每个单位对应的最大/最小值都设为自身
// 为上图的 1,2,3,4 的处理过程
for (i = 0; i & N; i++)
// compute values from smaller to bigger intervals
for (j = 1; 1 && j &= N; j++)
for (i = 0; i + (1 && j) - 1 & N; i++)
if (A[M[i][j - 1]] & A[M[i + (1 && (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
M[i][j] = M[i + (1 && (j - 1))][j - 1];
int **M: 二维数组，用于接收返回结果。其中第一维为从 i 个数字开始，第二维为表示 [i,i+2^j]的区间，数组值为最大/最小值在A数组中的位置。
int *A: 一位数组，为原数组。
int N: A的长度
求区间最值（O(1)）
当求 [a,b] 区间最值时，应找到两个长度为2^k的重叠区间，使得第一个区间的初始位置为 a，第二个区间的结尾位置为 b。那么第一个区间的最值即为M[a][k]，第二个区间最值为M[b+1-2^k][k]，再求出 ans=max(max1,max2)（或 ans=min(min1,min2)）
需要注意的是，上面求的 M[a][k] 和 M[d][k] 虽然有可能有重叠部分，但是由于查询时间复杂度为 常数，这里可以忽略
这道题是个奇葩题？
在 OpenJudge上的
线段树可过，POJ 却过不了
几乎就是模板题？（大雾
这个题是树的题，需要从根节点把dfs序记录下来并转成欧拉序，对欧拉序做区间最小值查询即为最近公共祖先。
err...不太友好的一点是卡vector，所以我换成链式前向星了
啥？链式前向星也卡？链式前向星+快速妥妥的A
#include &bits/stdc++.h&
using namespace
#define maxn 1000001
struct edge
edge edges[maxn];
int edges_size=0;
int first[maxn];
int dfs_list[maxn];
int dfs_list_size=0;
int dfn[maxn];
bool vis[maxn];
int first_pos[maxn];
int defaultdfn=1;
int _M[maxn][21];
int another_dfn[maxn];
void preprocess();
void process();
int getmin(int a,int b);
void connect();
void dfs(int i);
// 快速读入
int read()
int x=0,f=1;char c=getchar();
while(c&'0'||c&'9'){if(c=='-')f=-1;c=getchar();}
while(c&='0'&&c&='9'){x=x*10+c-'0';c=getchar();}
return x*f;
int main()
memset(first,-1,sizeof first);
N=read();M=read();root=read();
//cin&&N&&M&&
for(int i=0; i&N-1; ++i)
connect();
dfs(root);
preprocess();
for(int i=0; i&M; ++i)
process();
void connect()
x=read();y=read();
//cin&&x&&y;
edges[edges_size].to=y;
edges[edges_size].next=first[x];
first[x]=edges_size++;
edges[edges_size].to=x;
edges[edges_size].next=first[y];
first[y]=edges_size++;
void dfs(int i)
dfn[i]=defaultdfn++;
another_dfn[dfn[i]]=i;
dfs_list[dfs_list_size++]=dfn[i];
first_pos[dfn[i]]=dfs_list_size-1;
for(int j=first[i]; j!=-1; j=edges[j].next)
int nextp=edges[j].
if(!vis[nextp])
dfs(nextp);
dfs_list[dfs_list_size++]=dfn[i];
void process()
//cin&&x&&y;
x=read();y=read();
swap(x,y);
x=first_pos[x];y=first_pos[y];
printf("%d\n",another_dfn[getmin(x,y)]);
//cout&&another_dfn[getmin(x,y)]&&
int getmin(int a,int b)
int k=log2(b-a+1);
if((b-a+1)&(b-a))
int min1=dfs_list[_M[a][k]];
int min2=dfs_list[_M[b+1-(1&&(k))][k]];
return min1&min2?min1:min2;
return dfs_list[_M[a][k]];
void preprocess() {
int *A=dfs_
int N=dfs_list_
for (i = 0; i & N; i++)
_M[i][0] =
for (j = 1; 1 && j &= N; j++)
for (i = 0; i + (1 && j) - 1 & N; i++)
if (A[_M[i][j - 1]] & A[_M[i + (1 && (j - 1))][j - 1]])
_M[i][j] = _M[i][j - 1];
_M[i][j] = _M[i + (1 && (j - 1))][j - 1];
阅读(...) 评论()欲戴皇冠，必承其重！
51Nod 1174 求区间最大的数 RMQ
51Nod 1174 求区间最大的数 RMQ
题目链接：
在很多情况下， 我们求区间最大最小值都是用朴素的遍历算法，其复杂度是O(N)， 当存在多次区间最大最小查询时，若查询次数为Q， 那么算法负责度就是O(Q*N) 。 当查询次数 Q 很大时，我们就需要对算法进行优化了。常见的优化方法有： 使用树状数组或者线段树，或者是使用专门的RMQ算法。RMQ是一种专门用来求区间最大最小值的DP。
树状数组和线段树求区间最值，需要 O(N*log(N)) 的时间负杂度进行初始化，然后O(log(N))的时间负杂度进行查询。
RMQ算法求区间最值，需要O(N*log(N))的时间负杂度进行初始化，但是查询只需要O(1) 。
下面是我对RMQ算法的理解：
以求区间最大值为例，MAX[i][j] 表示的是从i 开始 长度为
2^j 的区间的最大值。
初始化的过程MAX[i][j] 表示的是区间 [i, i + (1 && j) - 1] 的最大值，区间长度是1&&j：
将区间 [i, i + (1 && j) - 1] 分成两个长度都为 1 && (j - 1) 的区间 ，令m = i + (1 && (j - 1)) - 1;[i, m]、[m + 1, m +
(1 && (j - 1)) - 1]，那么， 我们写出状态转移方程： MAX[i][j]
= max(MAX[i][j - 1], MAX[m + 1][j - 1])
= max(MAX[i][j - 1], MAX[ i + (1 && (j - 1))][j - 1])
查询过程假如查询区间为[L, R]。区间查询长度为 R - L + 1，令k = (int)log2(R
- L + 1)， 即小于区间长度的最大的2的幂次方。即k 满足大小关系2^k
&= (R-L+1)&=2^(k+1)，那么区间[L, R]的最大值就必在区间[L，L + (1 && k) - 1]，
或者区间[R-(1&&k) + 1,R]中。
#include &cmath&
#include &queue&
#include &vector&
#include &cstdio&
#include &string&
#include &cstring&
#include &iomanip&
#include &iostream&
#include &algorithm&
//#pragma comment(linker, "/STACK:,")
#define FIN
freopen("input.txt","r",stdin)
#define FOUT
freopen("output.txt","w",stdout)
#define fst
#define snd
#define lson
l, mid, rt && 1
#define rson
mid + 1, r, rt && 1 | 1
typedef __int64
//typedef long long LL;
typedef pair&int, int& PII;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MAXN = 10000 + 5;
const int MAXM = 50000 + 5;
const int MAXBIT = 16;
struct RMQ {
int MAX[MAXN][MAXBIT];
int log2[MAXN];
void init(int _n) {
log2[0] = -1;
for (int i = 1; i &= i ++) {
scanf("%d", &MAX[i][0]);
if (i) log2[i] = i & (i - 1) ? log2[i - 1] : log2[i - 1] + 1;
for (int j = 1; j &= log2[n]; j ++) {
for (int i = 1; i + (1 && j) - 1 &= i ++) {
MAX[i][j] = max(MAX[i][j - 1], MAX[i + (1 && (j - 1))][j - 1]);
int query(const int& L, const int& R) {
k = log2[R - L + 1];
return max(MAX[L][k], MAX[R - (1 && k) + 1][k]);
int main() {
#ifndef ONLINE_JUDGE
#endif // ONLINE_JUDGE
while (~scanf("%d", &N)) {
rmq.init(N);
scanf("%d", &Q);
while (Q --) {
scanf("%d %d", &a, &b);
a ++, b ++;
int res = rmq.query(a, b);
printf("%d\n", res);
没有更多推荐了，