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

Range Minimum Query and Lowest Common Ancestor

RMQ

Range Minimum Query and Lowest Common Ancestor

Range Minimum Query and Lowest Common Ancestor

Range Minimum Query and Lowest Common Ancestor

这个函数最多执行2 * sqrt(H)次操作。通过使用这个方法,我们得到了<O(N), O(sqrt(H))>的算法,这里H指的是树的高度。在最坏的情况下H=N,因此总的复杂度为<O(N), O(sqrt(N))>。这个算法的主要好处是易于编码(Division1中的程序员应该在15分钟内完成这段代码)。

Another easy solution in <O(N logN, O(logN)>

如果我们对这个需要一个更快的解决方法,我们可以使用动态规划。首先我们构建一张表P[1,N][1,logN],这里P[i][j]指的是结点i的第2j个祖先。为了计算这个值,我们可以使用下面的递归:

预处理的函数如下:

void process3(int N, int T[MAXN], int P[MAXN][LOGMAXN]) {

上一页第13页

你可能喜欢

热门文档

相关文档

  • 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