倍增思想复习

倍增，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];
	
}