RMQ（Range Minimum/Maximum Query），即区间最值查询
查询很多的时候求[l,r]的最大值可以弄一个数组f[i,j]表示i~j的最大值
//这个是线段树
rmq是f[i,j]表示 i 到 i+2^j-1 这个区间的最大值
/*给例子好理解
比如f[i,0] = a[i] 然后先要预处理这个f 方法是DP
f[i,j] = max( f[i,j-1] , f[ i + (1<<j-1) , j-1] )
相当于是二分
比如 2,4其实是2,18
那么 2~ 18 中间有16个数
我们求2~18的最值等于 2~10 和 11~18的最值的
我们求2~18的最值等于 2~10 和 11~18的最值的
最值用 rmq表示就是f[2,3]
初始化条件就是f[i,0]=a[i]
有了初始化有了动态转移方程就可以得到f了
现在假设来了一个请求 l~r
那么我们先要得到一个区间的大小就是r-l+1
找到一个K
这个K是 2^K<=r-l+1 的最大的K
然后就是ans= max( f[l,k], f[r-(1<<k)+1,k])
这个K是 2^K<=r-l+1 的最大的K
然后就是ans= max( f[l,k], f[r-(1<<k)+1,k])
假设是2~20区间长度是19K=4
就是 f[2,4] f[4,4]
换成线段树的表示就是
f[2,18] f[4,20]
这2段的最值就是f[2,20]的最值了
虽然有重复的部分 但是不影响
f[2,18] f[4,20]
这2段的最值就是f[2,20]的最值了
虽然有重复的部分 但是不影响
*/
LCA（最近公共祖先）
LCA就是把问题转化为RMQ
转化过程如下：
一棵树，我们对它先进行DFS，记录下路径
比如上图的这颗树（图来自百度，侵删）
DFS的结果是1 3 1 2 4 2 5 6 5 7
深度就是1 2 1 2 3 2 3 4 3 4
仔细想想会得到求 i~j 的路径就是上面那个路径的子集
//其实这个路径没写完整 后面还有1 3 1 2 4 2 5 6 5 7 5 2 1
记录深度和路径以及每一个节点第一次到达的时候一共走了几步
//对于1 2 3 4 5 6 7来说 他们分别是1 4 2 5 7 8 10
然后问题要求是求路径
比如求4 ~7 查一下
4第一次出现是5
7第一次出现是10
那么问题就是求1 3 1 2 4 2 5 6 5 7 5 2 1这个里面的第五个到第十个4 2 5 6 5 7
4第一次出现是5
7第一次出现是10
那么问题就是求1 3 1 2 4 2 5 6 5 7 5 2 1这个里面的第五个到第十个4 2 5 6 5 7
深度对应的是这6个数字 3 2 3 4 3 4
深度最小的那个就是他们的公共父节点
深度为2的那个路径上的2
问题就变成了求区间
假设：
路径是path[] 深度是dep[] 首次出现是first[]
求i~j就变成了f [ dep [ first[ i ] ] , dep [ first[ j ] ] ]
假设结果是 __min
在这段区间上搜索一下
if f[i]= __ min
那么保存i
公共父节点就是 path [ i ]
在这段区间上搜索一下
if f[i]= __ min
那么保存i
公共父节点就是 path [ i ]