RMQ算法求区间极值--倍增思想

int dp[MAX_N][log2(MAX_N)+2],a[MAX_N];//dp[i][j]代表从i开始长度为2的j次方的区间的最小值 void rmq_init(){ for(int i=1;i<=N;i++) dp[i][0]=a[i]; for(int j=1;(1<<j)<=N;j++){ for(int i=1;i+(1<<j)-1<=N;i++){ dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]); } } } int rmq(int l,int r){ int k=log2(r-l+1); return min(dp[l][k],dp[r-(1<<k)+1][k]); }