[tem]RMQ(st)

倍增思想

代码中有两个测试

#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5;
int a[N],f[N][21];

void init(int n){
    for(int i=1;i<=n;i++) f[i][0]=a[i];
    
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

int RMQ(int l,int r){
    int k=log(r-l+1)/log(2);    //2^k<=l~r
    return min(f[l][k],f[r-(1<<k)+1][k]);
}
int main(int argc, const char * argv[]) {

    //test beizeng
    //find 2^k<=l~r
    int l=93333338,r=137123411;
    int ans1,ans2;
    ans1=log(r-l+1)/log(2);　　　　　　　　　　//advise　　　　　
    while ((1<<(ans2+1))<=r-l+1) ans2++;
    printf("test1: %d %d

",ans1,ans2);

    
    //test beizeng
    //change into binary
    int n=33;
    for(int i=0;i<=16;i++)　　　　　　　　　　//advise
        if(n&(1<<i)) printf("t1: %d ",i);

    printf("
");
    for(int i=16;i>=0;i--)
        if(n>=(1<<i)) printf("t2: %d ",i),n^=(1<<i);
    return 0;
}