数据结构之——RMQ与LCA

RMQ英文是Range Maximum(Minimum) Query，是用来求取某个区间的最大值最小值，通常用在查询次数比较大的区间最值问题中。

RMQ的原理是动态规划，利用了倍增的思想。我们用A[1...N]表示一组数，[Li,Ri]表示题目涉及到的查询区间。

设F[i,j]表示从A[i]到A[i + (2^j) - 1]这个范围的最大值，也就是以A[i]为起点的连续2^j个数的最大值。由于元素个数是2^j，可以均分为两部分，每部分有2^j-1个数。整个区间的最大值肯定是前半部分的最大值和后半部分最大值的较大者，满足动态规划的最优子结构。

则动归方程为：f[i, j] = max(f[i, j-1], f[i+2^(j-1), j-1]，边界条件：f[i,0] = A[i]。

这样，就可以用nlog2n的复杂度预处理数组。对于查询区间[Li,Ri]，先求出满足2^x<=Ri-Li+1的最大的x值。那么[Li,Ri]的最大值为区间[Li, Li+(2^x)-1]和区间[Ri-(2^x)+1,Ri]的较大者，即max(f[Li,x], f[Ri-(2^x)+1,x])。

这样每次查询的时间复杂度与查询区间的长度无关，都是O(1)。

void RMQ()
{
	int i,j;
	for(i=1;i<=N;i++)
	{
		M[i][0]=A[i];
		S[i][0]=A[i];
	}
	for(j=1;(1<<j)<=N;j++)
	{
		for(i=1;i+(1<<j)-1<=N;i++)
		{
			M[i][j]=max(M[i][j-1],M[i+(1<<(j-1))][j-1]);
			S[i][j]=min(S[i][j-1],S[i+(1<<(j-1))][j-1]);
		}
	}
}

 

 

LCA英文是Least Common Ancestors，用来描述一棵有根树T中任意两个结点的公共祖先x，且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图，而LCA(T,u,v)即u到v的最短路上深度最小的点。

LCA问题的算法：

1.离线算法(Tarjan)

利用并查集优越的时空复杂度，可以实现O(n+q)的算法，q是查询次数。

Tarjan算法基于深度优先搜索。对于新搜索到的一个结点u，先创建由u构成的集合，再对u的每颗子树进行搜索，每搜索完一棵子树，这时候子树中所有的结点的最近公共祖先就是u了。

void LCA(int parent)       //从根节点开始
{
	p[parent] = parent;
	ancestor[findSet(parent)] = parent;
	for(int i = index[parent]; i != -1; i = e[i].next)
	{
		LCA(e[i].to);
		Union(parent,e[i].to);
		ancestor[findSet(parent)] = parent;
	}
	vis[parent] = true;
	if(parent == a && vis[b])	//要先将所有查询记录下来，这里只有一个查询：a与b的LCA
		printf("%d\n",ancestor[findSet(b)]);
	else if(parent == b && vis[a])
		printf("%d\n",ancestor[findSet(a)]);
}

 2.在线算法(RMQ)

一个nlog2n的预处理，O(1)的查询。

以下面一棵树为例：

           (1)

         /     \

       (2)     (7)

      /   \       \

    (3)  (4)     (8)

          /  \

         (5)  (6)

step1：

    按深度遍历树，记录访问顺序和相应的深度(2*n-1)，及每个节点第一次出现的位置。

    结点的访问顺序为:1 2 3 2 4 5 4 6 4 2 1 7 8 7 1

    相应的深度为：    0 1 2 1 2 3 2 3 2 1 0 1 2 1 0

    结点1—8第一次出现的次序为：1 2 3 5 6 8 12 13

step2：

    查询3和6的公共祖先，考虑3和6第一次出现的位置为3和8，即寻找序列2 1 2 3 2 3中的最小值，最小值为1，对应的点位2，则3与6的最近公共祖先为2。

step3：

    则对于给出的任意两个结点，找出它们第一次出现的位置i,j(i<j)，在深度序列中查询最小值的下标k，depth[k]即为所求。显然，查询多次深度序列中的最小值的下标，自然而然联系到前面的RMQ。

int dfs[2*MAX];		//记录dfs搜索到的结点
int depth[2*MAX];	//相应的深度
int first[MAX];		//结点第一次被访问出现的位置
int top;			//记录dfs搜索的总次数
int f[2*MAX][15];		//f[i][j]表示depth从i到i+2^j-1中的最小值的下标

void RMQ()
{
	int i,j;
	for(i = 1; i <= top; i++)
		f[i][0] = i;
	for(j = 1; (1<<j) <= top; j++)
	{
		for(i = 1; i+(1<<j)-1 <= top; i++)
		{
			f[i][j] = depth[f[i][j-1]] < depth[f[i+(1<<(j-1))][j-1]] ? f[i][j-1] : f[i+(1<<(j-1))][j-1];
		}
	}
}

int query(int left, int right)
{
	int t;
	if(left > right)
	{
		t = left;
		left = right;
		right = t;
	}
	int k = (int)(log((right-left+1)*1.0)/log(2.0));
	int min = depth[f[left][k]] < depth[f[right-(1<<k)+1][k]] ? f[left][k] : f[right-(1<<k)+1][k];
	return dfs[min];
}

//main

DepthFirstSearch(i,0);
RMQ();
printf("%d\n",query(first[a],first[b]));//查询a和b的公共祖先

 

 

参考：poj3264 1330