Localhost8080

RMQ问题与LCA问题

topcoder上关于RMQ问题的精彩讲解

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

一、区间最小/ 最大查询(Range Minimum/Maximum Query) ：RMQ 问题
RMQ作为学习Suffix Array的基本知识之一，我想在写SA总结之前写下这一部分的知识。

RMQ问题可以算是经典问题中的经典，目的就是希望用较短的时间完成求区间最小值的操作。

方法有很多种，最简单的直接线性统计的效率极其低下，也比较白痴，差不多都应该会。

下面讲下几个比较好的RMQ问题的算法。

方法一：线段树

线段树作为维护区间性质的最佳利器，绝对是不错的选择。写起来可以递归，非常的方便。

但是他也是有缺点的，最大的问题就是虽然说是O(nlogn)-O(logn)的时间复杂度中的常数比较大。从实际运行效率上看不是很好。

我前面的日志里面写过一些线段树的题，线段树的用法大同小异，也比较好学，这里不再赘述。

方法二：RMQ的ST算法

ST算法是一个很不错的算法，复杂度为O(nlogn)-O(1)。这种算法运用的主要思想是倍增思想。

倍增思想的核心就是，通过递推使得结论成倍地提高。

这里我们定义这样一个数组f[i,j]表示从i开始向后数2j个元素的RMQ

递推方程就是

           f[i,j]:=min(f[i,j-1],f[i+1 shl (j-1),j-1]);

边界：f[i,0]:=a[i];

这样我们就可以用这样的式子来解决RMQ问题：

设k:=trunc(ln(j-i+1)/ln(2))

          RMQ(i,j):=min(f[i,k],f[j-(1 shl k)+1,k]);

对于某一些特殊的RMQ问题还有O(n)-O(1)的算法，方法在于分成长度特殊的段，然后再用这些段RMQ。这是将LCA问题转化为RMQ问题的途径。

方法三：笛卡尔树

这个方法的精髓在于将RMQ问题转化为LCA问题。

笛卡尔树的定义是，对于一个数组A来说，笛卡尔树的根的编号是这个数组的最小值的所在的编号k。他的左子树就是在数组A[1..k-1]上的一棵笛卡尔树，右子树是一棵在数组A[k+1..n]的一棵笛卡尔树。

这样RMQ(A,i,j)就被转化成了LCA(T,i,j)。

因为LCA问题离线Tarjan算法的复杂度是O(n)的，所以这个问题最终的复杂度在O(n)。

我的理解就是理论性比较强，并没有什么实际意义。

缺点是不支持在线提问。

以上就是RMQ问题的几种经典方法，如果想要透彻的理解好线段树和倍增法，还是需要一些题目的磨练。

//Toj: 2762

[ 描述] 已知长度为L 的数列A ，询问区间[l, r] 中的最值。

若询问的次数较少，可以用线性的复杂度来查询，但如果询问的次数过多且L 过大，那么复杂度就会很高。所以需要更快速的查找方法。

ST 算法：预处理O(nlogn) ，查询指定区间的最值O(1)

    把待求区间[l, r] 分为两段长为len 的区间，左边一段为[l, l+len-1] ，右边一段为[r-len+1, r] ，len 必须使得两段区间覆盖待求区间。

    设所求数组为W ：

    那么，所求最小值就是两个区间的最小值的最小值：

即Min(Min{W[i], l<=i<=l+len-1}, Min{W[j], r-len+1<=j<=r})

若都在预先处理中先求得两个区间的最小值，则每次查询的复杂度都是O(1) 。

预处理：（DP ）

    设dp[i][j] 表示从第i 个数起连续2^j 个数中的最值。

    dp[i][0]=a[i] 1<=i<=N

    dp[i][j]=Min(dp[i][j-1], dp[i+2^(j-i)][j-1])

求最值：把区间[l, r] 分成两个长度为2^n 的区间。

    为使区间被分解后，长度为2^n ，区间部分可重叠，但不可越过[l, r] 。

    例如 [3, 9] à [3, 6]+[6, 9] 即：dp[3, 2] 和dp[6, 2]

 

注：Dmin 与Dmax 用前清零。

将RMQ 拓展到二维状况时，依然使用ST 算法先进行预处理，再进行查询。其中可以有两种做法（以取最大值为例），对于数字矩阵num[1..M][1..N] ，取其中一个子矩阵的最大值。第一种方法：Dmax[x][y][i][j] 表示对于点(x, y) 为左上点，(x+2^i-1, y+2^j-1) 为右下点的子矩阵的最大值。在询问时，将待查询矩阵一分为四取最大值即可。

 toj 3375

 

第二种方法：是Dmax[x][y][i] 记录以(x, y) 为左上点，(x+2^i-1, y+2^i-1) 为右下点的正子矩阵的最大值。在询问时，也需要将待查询矩阵分为若干正子矩阵，取最大值即可。

第二种方法由于比第一种方法在Dmax 上少了一个维度，所以大大的节省了空间。

 

一、 最近公共祖先( Lowest Common Ancestors ) ：LCA 问题

//Toj: 3361 1051

    对于有根树T 的两个结点u 、v ，最近公共祖先LCA(T, u, v) 表示一个结点x ，满足x 是u 、v 的祖先且x 的深度尽可能大。另一种理解方式是把T 理解为一个无向无环图，而LCA(T, u, v) 即u 到v 的最短路上深度最小的点。

    解决LCA 主要是用最经典的Tarjan 离线算法，需要用到并查集来辅助。

1 、在并查集中建立仅包含x 结点的集合，即Fa[x]=x;

2 、处理x 的所有孩子，处理完每个孩子后，令Fa[ 孩子]=x ，即将孩子和x 所在集合合并；

3 、全部孩子处理完后，将x 标记为处理结束；

4 、处理所有与x 相关的询问。对于每个询问LCA(x, y) ，若y 已被标记，则记录下LCA(x, y)=Find(y) ，即y 所在集合的代表元素。

[ 模板] ( 以3361 为例)

在处理询问的时候需要建立关联序列表，另外调用LCA 时候必须调用根结点。

在查询的时候根据题意修改。

 

 二、 LCA 与RMQ ：

// 资料：RMQ 与LCA 问题( 郭华阳).ppt

RMQ 向LCA 转化：设序列A 的长度为N

    1 、设序列中最小值为为Ak ，建立优先级为Ak 的根结点Tk ；

    2 、将A[1..k-1] 递归建树作为Tk 的左子树；

3 、将A[k+1..N] 递归建树作为Tk 的右子树。

RMQ(A, i, j) 查询A[i..j] 的最值即为LCA(T, i, j) 。

LCA 向RMQ 转化：

    对有根树T 进行DFS ，将遍历到的结点按照顺序记下，得到一个长度为2*N-1 的序列，称之为T 的欧拉序列F ，每个结点在欧拉序列中出现，记录pos[u] 为结点u 在欧拉序列中

第一次出现的位置。

    LCA(T, u, v)=RMQ(B, pos(u), pos(v))


RMQ与LCA算法
1、RMQ问题的ST算法

如果一个算法的预处理时间为f(n)，查询时间为g(n)，则我们称这个算法的总复杂度为<f(n),g(n)>。

2、 RMQ问题的线段树解法

线段树（区间数）：

线段树是可以用于统计的一种非常优秀的数据结构，同样可以很好的解决RMQ问题。线段树又叫区间树，顾名思义，就是分区间来保存和查询所要处理的信息。

可以这样定义线段树：

struct node

{

    int left, right; // 区间的左边界和右边界

    int idx; // 这个区间内最小的值的序号

    node *l, *r; // 这个区间的左儿子和右儿子

};

node root; // 整个区间树的根节点     

然后初始化的函数：

void init(int left, int right, node *ptr)

{

    ptr->left=left, ptr->right=right;

    if (left==right)

    {

        ptr->l=NULL, ptr->r=NULL;

        ptr->idx=left;

        return;

    }

node *p=new node;

node *q=new node;

int mid=(left+right)/2;

init(left, mid, p);

init(mid+1, right, q);

ptr->l=p, ptr->r=q;

if (A[p->idx] < A[q->idx])

ptr->idx=p->idx;

else

ptr->idx=q->idx;

}

初始化的时候，调用语句：

init(0, N-1, &root);

查询RMQ(L, R)的函数：
int query(int L, int R, node *ptr)
{

if (L<=ptr->left && R>=ptr->right)

return ptr->idx;

int res;

int temp=0x7fffffff;

int mid=(ptr->left+ptr->right)/2;

i f (L<=mid)

{

int k=query(L, R, ptr->l);

temp=A[k];

res=k;

}

if (R>=mid+1)

{

int k=query(L, R, ptr->r);

if (A[k]<temp)

res=k;

}

return res;
}

查询的时候，调用语句：

int idx=query(L, R, &root);

用线段树解决RMQ问题的总复杂度是 <O(N), O(logN)> 。

用ST算法和用线段树解决RMQ问题各有自己的优先。只有查询的时候用ST算法和线段都可以解决，可以根据实际情况选择最优的算法。但是要修改数组中的值的时候，就只能用线段树来做了，ST算法不支持修改， 线段树的修改复杂度是O(logN)的 。

3、 LCA问题及其与RMQ问题间的转换

在一颗树上，两个节点p和q的最近公共祖先就是离根节点最远的p和q的祖先。下面介绍一种简单的算法（ 类似于RMQ问题的ST算法的思想 ）。

定义下列数组：

I nt T[N]; // T[i]代表节点i的父节点，根节点的父节点为-1

I nt L[N]; // L[i]代表节点i的高度，根节点的高度为1

I nt P[N][logN]; // P[i][j]代表节点i的第(1<<j)个祖先

运用动态规划的思想，状态转移方程如下：

if (j==0)

p[i][j]=T[i];

else

p[i][j]=p[P[i][j-1]][j-1];

预处理的函数如下：

void ptrprocess()

{

      for (i=0; i<N; i++)

      for (j=0; (1<<j)<N; j++)

      P[i][j]=-1;

      for (i=0; i<N; i++)

      P[i][0]=T[i];

      for (j=1; (1<<j)<N; j++)

      for (i=0; i<N; i++)

      if (P[i][j-1]!=-1)

      P[i][j]=P[P[i][j-1]][j-1];
}

查询LCA(p, q)的函数如下：

int query(int p, int q)

{

      // 不失一般性，让p节点的高度始终大于q节点的高度

      if (L[p]<L[q])

      swap(p, q);

      // 计算log(L[p])的值

      int log;

      for (log=0; (1<<log)<L[p]; log++) ;

      log--;

      // 计算节点p的与节点q在同一高度上的祖先

      for (i=log; i>=0; i--)

      if (L[p]-(1<<i) >= L[q])

      p=P[p][i];

      // 如果节点p的祖先是q，就返回节点p

      if (p==q)

      return p;

      // 节点p，q在同一高度上，计算LCA(p,q)

      for (i=log; i>=0; i--)

      if (P[p][i]!=-1 && P[p][i]!=P[q][i])

      {

            p=P[p][i];

            q=P[q][i]; 
            }

            return T[p];
}

这个算法的总复杂度是 <O(NlogN), O(logN)> 的。

LCA问题转化为RMQ问题：

先用深度优先搜索求出树的欧拉序列，然后建立一下信息：

int E[2*N]; // 树的欧拉序列（前序，中序，后序都可以）

int L[2*N]; // L[i]对应着E[i]的高度

int F[2*N]; // F[i]代表节点i第一次在欧拉序列中出现的位置

求节点p和q的的最近公共祖先。在欧拉序列中，节点p第一次出现的位置F[p]，节点q第一次出现的位置F[q]，位置F[p]和F[q]之间的高度最小的节点就应该是LCA(p, q)，而这个高度最小的节点则可以通过对L序列求RMQ(F[p], F[q])得到，所以最后总结出 LCA(p,q)=E[RMQ(F[p],F[q])] 。

而将LCA问题转化为RMQ问题的复杂度是 O(N) 的。

推荐题目：

http://acm.pku.edu.cn/JudgeOnline/problem?id=2104

http://acm.pku.edu.cn/JudgeOnline/problem?id=2763

posted on 2010-05-08 12:11 superKiki 阅读(2610) 评论(0)  编辑 收藏 引用