算法合集之rmq与lca问题.pptx

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