RMQ求解 ST 线段树 ......

ST算法

#include<cmath>
//预处理
void ST_pre(){
    for(int i=1;i<=n;i++){
        f[i][0]=a[i];
    }
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1)][j-1]);    
        }
    }
}

//区间[l,r]的最大值查询
int ST_query(int l,int r){
    int k=log(r-l+1)/log(2);
    return max(f[l,k],f[r-(1<<k)+1][k]);
}

线段树

树结点的第k个祖先

树结点的第k个祖先
dp[i][j]表示节点i第2^j个祖先

class TreeAncestor {

    int[][] dp;
    public TreeAncestor(int n, int[] parent) {
        int m=0;
        for(int i=1;i<=n;i*=2){
            m++;//最大深度
        }
        dp=new int[n][m];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],-1);
        }
        //初始化
        for(int i=0;i<n;i++){
            dp[i][0]=parent[i];
        }
        //预处理递推
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++){
                if(dp[i][j]==-1){
                    continue;
                }
                dp[i][j]=dp[dp[i][j-1]][j-1];
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for(int i=0;i<16;i++){
            if((k&(1<<i))!=0){
                node=dp[node][i];
            }
            if(node==-1){
                break;
            }
        }
        return node;
    }
}