RMQLCA问题与ST(SparseTable)算法.doc

RMQ/LCA问题与ST(Sparse Table)算法RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。你当然可以写个O(n)的,但是万一要询问最值1000000遍，估计你就要挂了。这时候你可以放心地写一个线段树（前提是不写错）O（logn)的复杂度应该不会挂。但是，ST算法，它可以做到O(nlogn)的预处理，O(1)地回答每个询问。来看一下ST算法是怎么实现的(以最大值为例): 首先是预处理，用一个DP解决。设ai是要求区间最值的数列，fi, j表示从第i个数起连续2j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f1，0表示第1个数起，长度为20=1的最大值，其实就是3这个数。f1，2=5，f1，3=8，f2，0=2，f2，1=4从这里可以看出fi,0其实就等于ai。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把fi，j平均分成两段（因为fi，j一定是偶数个数字），从i到i+2(j-1)-1为一段，i+2(j-1)到i+2j-1为一段(长度都为2（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。fi，j就是这两段的最大值中的最大值。于是我们得到了动规方程Fi, j=max（Fi，j-1, Fi + 2(j-1)，j-1） 接下来是得出最值，也许你想不到计算出fi，j有什么用处，一般毛想想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间2，8的最大值，就要把它分成2,5和5,8两个区间，因为这两个区间的最大值我们可以直接由f2，2和f5，2得到。扩展到一般情况，就是把区间L，R分成两个长度为2n的区间（保证有fi，j对应）。直接给出表达式：k := ln(R-L+1) / ln(2);ans := max(FL，k, FR - 2k+1, k);这样就计算了从i开始，长度为2t次的区间和从r-2i+1开始长度为2t的区间的最大值（表达式比较烦琐，细节问题如加1减1需要仔细考虑.另外还有一篇RMQ问题和LCA问题/s/blog_40d4357f010004ug.html最近公共祖先与RMQ问题一、最近公共祖先(Least Common Ancestors)对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。这里给出一个LCA的例子：例一对于T=V=1,2,3,4,5E=(1,2),(1,3),(3,4),(3,5)则有：LCA(T,5,2)=1LCA(T,3,4)=3LCA(T,4,5)=3-二、RMQ问题(Range Minimum Query)RMQ问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j=n)，返回数列A中下标在i,j里的最小值下标。这时一个RMQ问题的例子：例二对数列：5,8,1,3,6,4,9,5,7 有：RMQ(2,4)=3RMQ(6,9)=6RMQ问题与LCA问题的关系紧密，可以相互转换，相应的求解算法也有异曲同工之妙。下面给出LCA问题向RMQ问题的转化方法。对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的深度存入数组E最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做Ri。如果结点Ei的深度记做Di，易见，这时求LCA(T,u,v)，就等价于求ERMQ(D,Ru,Rv)，(RuRv)。例如，对于第一节的例一，求解步骤如下：数列Ei为：1,2,1,3,4,3,5,3,1Ri为：1,2,4,5,7Di为：0,1,0,1,2,1,2,1,0于是有：LCA(T,5,2) = ERMQ(D,R2,R5) = ERMQ(D,2,7) = E3 = 1LCA(T,3,4) = ERMQ(D,R3,R4) = ERMQ(D,4,5) = E4 = 3LCA(T,4,5) = ERMQ(D,R4,R5) = ERMQ(D,5,7) = E6 = 3易知，转化后得到的数列长度为树的结点数的两倍减一，所以转化后的RMQ问题与LCA问题的规模同次。ST算法举例：POJ 3264 /JudgeOnline/problem?id=3264参见 /Victordu/archive/2008/09/18/50429.htmlconst int size = 50001;int minNumsize16;int maxNumsize16;int main() int n, m; scanf(%d%d, &n, &m); for(int i=1; i=n; i+) int t; scanf(%d, &t); minNumi0 = t; maxNumi0 = t; for(int j=1; j=log(double)n)/log(2.); j+) for(int i=1; i=n; i+) minNumij = minNumij-1; maxNumij = maxNumij-1; if(i + (1(j-1) = n) minNumij = min(minNumij, minNumi + (1(j-1)j-1); maxNumij = max(maxNumij, maxNumi + (1(j-1)j-1); for(int i=0; i right) int t = left; left = right; right = t; int k = floor(log(double)right - left + 1)/log(2.); printf(%dn, max(maxNumleftk, maxNumright - (1k) + 1k) - min(minNumleftk, minNumright - (1k) + 1k); return 0;ST算法求解RMQ问题 RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。可以写一个线段树，但是预处理和查询的复杂度都是O（logn)。这里有更牛的算法，就是ST算法，它可以做到O(nlogn)的预处理，O(1)！地回答每个询问。 来看一下ST算法是怎么实现的(以最大值为例）： 首先是预处理，用一个DP解决。设ai是要求区间最值的数列，fi,j表示从第i个数起连续2j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f1，0表示第1个数起，长度为20=1的最大值，其实就是3这个数。f1，2=5，f1，3=8，f2，0=2，f2，1=4从这里可以看出fi,0其实就等于ai。这样，Dp的状态、初值都已经有了，剩下的就是状态转移方程。我们把fi，j平均分成两段（因为fi，j一定是偶数个数字），从i到i+2(j-1)-1为一段，i+2(j-1)到i+2j-1为一段(长度都为2（j-1）)。用上例说明，当i=1，j=3时就是3,2,4,5 和 6,8,1,2这两段。fi，j就是这两段的最大值中的最大值。于是我们得到了动规方程Fi,j=max（Fi，j-1,Fi+2(j-i)，j-1）. 接下来是得出最值，也许你想不到计算出fi，j有什么用处，一般毛想想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O（1）。还是分开来。如在上例中我们要求区间2，8的最大值，就要把它分成2,5和5,8两个区间，因为这两个区间的最大值我们可以直接由f2，2和f5，2得到。扩展到一般情况，就是把区间l，r分成两个长度为2n的区间（保证有fi，j对应）。直接给出表达式：fi,j 表示 从第 i 个数数 2j 中最小的数那么：最大值 fi,j=max(fi,j-1,fi+2(j-1),j-1); 最小值 fi,j=min(fi,j-1,fi+2(j-1),j-1);模板： #include#include#definemax(a,b)(a)(b)?(a):(b)#definemin(a,b)(a)(b)?(a):(b)usingnamespacestd;constintmaxn=50001;inthmaxn;intmxmaxn16,mnmaxn16;intn,q;voidrmq_init()inti,j;for(j=1;j=n;j+)mxj0=mnj0=hj;intm=floor(log(double)n)/log(2.0);for(i=1;i0;j-)mxji=mxji-1;if(j+(1(i-1)=n)mxji=max(mxji,mxj+(1(i-1)i-1);for(i=1;i0;j-)mnji=mnji-1;if(j+(1(i-1)=n)mnji=min(mnji,mnj+(1(i-1)i-1);intrmq(intl,intr)intm=floor(log(double)(r-l+1)/