-
2007-05-03
RMQ和LCA - [我的OI]
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://iuaaui.blogbus.com/logs/5241135.html
好不容易找到一篇GHY的论文（WC2007）,看过之后稍有些明白。
RMQ是给定一列数，动态询问［i,j］区间内的最小（或最大值）。
LCA是给定一棵树，动态询问u和v的最近公共祖先。
解决这两种问题都有个很重要的倍增思想（这个思想在后缀数组方面亦有所应用）。
关键需要记住的是
在LCA预处理的时候
p[i,j] 表示i的2^j 倍祖先
那么就有一个递推式子 p[i,j]=p[p[i,j-1],j-1]RMQ和LCA可以相互转化。。 所以只要记住一种就行了。。
RMQ转LCA的时候是生成一棵类似于堆的递归树；LCA转RMQ的时候用到的是深度优先遍历。
主要掌握的不在于算法，而是在于倍增思想历史上的今天：
可重复的排列&可重复的组合 2007-05-03NOI2006_DAY1_Network_sol 2007-05-03NOI2006_DAY2_Profit_sol 2007-05-03第一次写博客 2007-05-03随机文章：
省选失败 2007-06-10IPSC—TOTALLY UNLUCKY 2007-05-12三分法单谷求极值 2007-05-05PKU-South Central China 2007(1) 2007-05-04可重复的排列&可重复的组合 2007-05-03
收藏到：Del.icio.us
评论
不过比起，O(n)-->O(1)，还是非常非常实用的。
主要思想是块状链表，
递推式是 T(n)=T(sqrt(n))+n
解得 T(n)=O(log log n)
这都是在 adn.cn上看到的。
P.S. 申请链接。