Chinaunix首页 | 论坛 | 博客
  • 博客访问: 586499
  • 博文数量: 197
  • 博客积分: 7001
  • 博客等级: 大校
  • 技术积分: 2155
  • 用 户 组: 普通用户
  • 注册时间: 2005-02-24 00:29
文章分类

全部博文(197)

文章存档

2022年(1)

2019年(2)

2015年(1)

2012年(100)

2011年(69)

2010年(14)

2007年(3)

2005年(7)

分类: C/C++

2011-11-11 14:40:02

原文见
写得很清晰

注释:
Sparse Table (ST) algorithm 小节
process2的M[i][j]和上面的公式偏差one, 公式应该是错的,process2中的应该正确.

Segment trees小节
segment tree的query函数居然修改节点, 通常不应该这样.
  所以应该移去诸如
return M[node] = p2;
中 "M[node] ="

Lowest Common Ancestor (LCA) 的An solution

先尝试两个节点的上一层section,如果section号相同标明LCA介于当前位置和上一层section之间,顺序检查即可。否则直接挪到上一层section。


 "From RMQ to LCA" 小节前面的那个图 LCAT(10, 15)应该为LCAT(9, 12)

From RMQ to LCA 小节
"At the i-th step A[i] will be added next to the last element in the stack that has a smaller or equal value to A[i], and all the greater elements will be removed. The element that was in the stack on the position of A[i] before the insertion was done will become the left son of i, and A[i] will become the right son of the smaller element behind him."
这段话比较绕口, 直接看下面的例子即可, 尤其是behind 似乎应该为before

computerTree 的参数连T[]数组都没有交代,从代码看T[i]纪录的是i的父亲



阅读(681) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~