LCA 最近的公共祖先

eg：LCA（1，2） = 1

image-20200620191409657.png

三种算法：
暴力算法
倍增
dfs+st
离线算法

在线：问一次算一次
离线：问完后一次性算出

倍增：DP

暴力法的优化（与二进制关联）

image-20200620191321867.png

image-20200620191551315.png

树的创建：无向图

使用添加边的方式构建

image-20200620192810605.png

搜索操作：dfs或bfs（队列）

tarjan

image-20200620195646407.png

image-20200620195901761.png

image-20200620200023581.png

image-20200620200351968.png

RMQ问题：区间的最值问题

稀疏表ST在线解决RMQ

image-20200620191551315.png