RMQ 一维模板_潮鸣り

void intRMQ(int n,int b[])
{
    mm[0]=-1;
    for(int i=1; i<=n; ++i)
    {
        mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; 
                //计算长度 n为2的倍数 n&n-1==0
        dp[i][0]=b[i];  //初值
    }
    for(int j=1; j<=mm[n]; ++j)  //for(int j=1;(1<<j)<=n;++j)
        for(int i=1; i+(1<<j)-1<=n; ++i)
        {
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
          //maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);
          //minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);
        }

}

int rmq(int x,int y)
{
    int k=mm[y-x+1];
    return max(dp[x][k],dp[y-(1<<k)+1][k]);
    
}void intRMQ(int n,int b[])
{
    mm[0]=-1;