RMQ&LCA 问题
湖南省长郡中学 郭华阳
全文总揽
问题的提出
问题的解决
问题的应用
I. 问题的提出
问题的提出
LCA ：基于有根树最近公共祖先问题
LCA （ T ， u ， v ）：在有根树 T 中，询问
一个距离根最远的结点 x ，使得 x 同时为结点
u 、 v 的祖先
问题的提出
RMQ ：区间最小值询问问题
RMQ （ A ， i ， j ）：对于线性序列 A 中，
询问区间 [i ， j] 上的最小值
特别的，若线性序列 A 任意两相邻元素相差为
±1
±1
，那么建立在
，那么建立在
A
A
上的
上的
RMQ
RMQ
称为
称为
±1
±1RMQ
