倍增，st表复习
众所周知，st表是倍增思想的一种实现罢了
然后呢，倍增思想最重要应用于RMQ和LCA问题
都很重要，然而我还不会背，所以拿今晚一半时间左右来复习这个。
其实不用背，重在理解：
st表：注意先枚举2的多少次方（不然后面长的区间靠短的两个区间拼合，短的还没处理完的话是无法做的）
然后查询的时候要求左端点开始长度为k查一次，右端点长度为k向左查一次（其实就是找左端点而已）
为甚？因为我log2(r-l+1)是向下取整的，否则可能遍历不到。如果用大于k的会导致查询的区域过多而wa
https://www.luogu.com.cn/problem/P3865
https://www.luogu.com.cn/record/116834836
然后LCA：
https://www.luogu.com.cn/problem/P3379
https://www.luogu.com.cn/record/116834022
tarjan算法我是会的了，不再赘述，但是倍增算法非常有用，想查就查，而tarjan只能离线处理
首先只要会了st表，LCA就会一半了。fa(x,j)很好转移,一样是先向上跳一半，再跳一半这个意思
注意：由于我dfs到一个点，此时他之上的所有点都已经统计完了，所以进到这个点就立即计算数组，不会有问题的
关键是向上找的过程
首先是统一深度，深得那个点往上跳
然后再一起往上跳
注意三点：
1.还是因为log2是向下取整的，所以我不一定一次就能把深的点和浅的点统一深度
2.一起向上跳前，先判断下两者是不是到同一个点了
3.我向上跳还是由大到小这么跳，因此很有可能存在两个点跳过的情况，不能取这个答案
解决办法就是我尽力向上跳，两者要是跳到同一个点continue，那么最后两者能到的就是LCA 的两个儿子
return fa(x,0)即可
st代码：
for(int j=0;j<=18;j++){//注意先美剧倍数
for(int i=1;i<=n;i++){
if(j==0){
st[i][0]=num[i];
continue;
}
else
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
while(m--){
int l,r;
l=read();
r=read();
//注，区间长度要求:l+2的x次方-1=R
//解得x=k=log2(r-l+1)
int k=log2(r-l+1);
printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k])) ;
}
LCA重要函数：
void dfs(int x,int fa){
fat[x][0]=fa;//注意初始化
for(int j=1;j<=19;j++){
fat[x][j]=fat[fat[x][j-1]][j-1];//往上一半一半的跳
}//因为上面的都统计过了，所以现在dfs到这个点一定是可以统计的
dep[x]=dep[fa]+1;//这是为了后面lca好找
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
dfs(to,x);
}
}
int getlca(int x,int y){
if(dep[x]>dep[y]){
swap(x,y);//注意不要swap dep数组了 ,x换到深的那里
}//让x在上方
for(int i=19;i>=0;i--){//还是一定要记住log2向下取整，所以不一定一次就可以跳到，这时候应该跳离depx最近的，所以从大到小美剧，而且每一次跳的比
//上一次肯定少，所以一遍i即可
//另：从小到大枚举不就相当于一次走一位吗
if((dep[y]-(1<<i))>=dep[x]){
y=fat[y][i];
}
}
if(x==y){
return x;
}
for(int i=19;i>=0;i--){
if(fat[x][i]==fat[y][i])//因为可能都跳过了
continue;
else{
x=fat[x][i];
y=fat[y][i];
}
}
return fat[x][0];
}