RMQ的樹狀數(shù)組實現(xiàn)：

#include <stdio.h> #define N 100005int idx[N]; int num[N]; int n,m,l,r,i,j;int min(int a,int b) {return a<b? a:b; }int lowbit(int x) {return x&(-x); }void init() {for(i=1;i<=n;i++){idx[i]=num[i];for(j=1;j<lowbit(i);j<<=1)idx[i]=min(idx[i],idx[i-j]);} }int query(int l,int r) {int ans=num[r];while(1){ans=min(ans,num[r]);if(l==r) break;for(r--;r-l>=lowbit(r);r-=lowbit(r))ans=min(ans,idx[r]);}return ans; }int main() {while(~scanf("%d%d",&n,&m)){for(i=1;i<=n;i++)scanf("%d",&num[i]);init();while(m--){scanf("%d%d",&l,&r);printf("%d\n",query(l,r));}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的RMQ问题(区间求最值)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。