void rmq_init() { for(int i=1;i<=N;i++) dp[i][0]=arr[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]); }
rmq查询过程
假设我们需要查询区间[l ，r]中的最小值，令k = ， 则区间[l, r]的最小值RMQ[l,r] = min(dp[l][k], dp[r - (1 << k) + 1][k]);
但是为什么这样就可以保证是区间最小值了呢？
dp[l][k]维护的是区间 [l, l + 2^k - 1] , dp[r - (1 << k) + 1][k]维护的是区间 [r - 2^k + 1, r] 。
那么只要我们保证 ≤ 就能保证RMQ[l,r] = min(dp[l][k], dp[r - (1 << k) + 1][k])；
————————————————
int rmq(int l,int r) { int k=log2(r-l+1); return min(dp[l][k],dp[r-(1<<k)+1][k]); }