原文见
写得很清晰
注释:
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的父亲
阅读(737) | 评论(0) | 转发(0) |
