文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > Range Minimum Query and Lowest Common Ancestor
侵权投诉

Range Minimum Query and Lowest Common Ancestor

RMQ

注意L中连续的元素相差为1。

From RMQ to LCA

我们已经看到了LCA问题可以在线性时间规约到RMQ问题。现在让我们来看看怎样把RMQ问题规约到LCA。这个意味着我们实际上可以把一般的RMQ问题规约到带约束的RMQ问题(这里相邻的元素相差1)。为了达到这个目的,我们需要使用笛卡尔树。 对于数组A[0,N-1]的笛卡尔树C(A)是一个二叉树,根节点是A的最小元素,假设i为A数组中最小元素的位置。当i>0时,这个笛卡尔树的左子结点是A[0,i-1]构成的笛卡尔树,其他情况没有左子结点。右结点类似的用A[i+1,N-1]定义。注意对于具有相同元素的数组A,笛卡尔树并不唯一。在这篇教程中,将会使用第一次出现的最小值,因此笛卡尔树看作唯一。可以很容易的看到RMQA(i, j) = LCAC(i, j)。 下面是一个例子:

Range Minimum Query and Lowest Common Ancestor

上一页第18页

你可能喜欢

热门文档

相关文档

  • RMQ[ENGLISH]

    Range Minimum Query and Lowest Common Ancestor By danielp TopCoder Member Introduction Notations Range Minimum Query (RMQ) Trivial algorithms for RMQ A <O...

  • 最近公共祖先LCA、打印螺旋矩阵

    Topcoder 上有一篇详细阐述 RMQ 问题的“ Range Minimum Query and Lowest Common Ancestor ”,网上也有翻译版。在此,我来简单引用 & 总结下。至于为何要总结 ...

  • Lowest Common Ancestor

    The lowest common ancestor is defined between two nodes v and w as the ... Range Minimum Query an... 23页 1下载券 Range Minimum Query an... ...

  • ACM之数据结构

    RMQ:Range Minimum Maximum Query – 在一个序列上,给定区间,求区间极值 ? LCA:Lowest Common Ancestor – 最近公共祖先是一个节点,是指定两点的祖先, 且深度...

  • XML数据的查询技术

    (smallest lowest common ancestor) problem, and ...Query instances of XQuery FT and XML IR/fragment...Structural join of XML based on range partitioning...

  • - (parent-child) , - (ancestor-descendant)

    (smallest lowest common ancestor); dewey encoding;...Query instances of XQuery FT and XML IR/fragment...Structural join of XML based on range partitioning...

  • 工学类工学特论

    lca = lowest common ancestor ? u = lca(v,w): v と w の共通の祖先 ...5 6 7 8 9 10 11 u v mw 5 6 13 Range Minimum Query 问题 (RMQ) ...

  • V. Theoretical and practical improvements on the RM...

    Abstract. The Range-Minimum-Query-Problem is to preprocess an array such ...1 Introduction The problem of ?nding the lowest common ancestor (LCA) of ...

  • 二叉树演绎于结点序号内蕴性质的快速算法

    Key words:algorithm design; binary tree; inorder traversal; query fast 摘要...[18] Daniel P.Range minimum query and lowest common ancestor[EB/OL]. ...

  • RMQ和LCA讲稿

    // 与根结点U合并(并查集操作) Find(u).ancestor?:=?u?? // 将u所在...57、P94? ②《Range? Minimum? Query? and? Lowest? Common? Ancestor》by?...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email