第一种实现方法是dp, 我们定义dp[i][j]为从i位置开始长度为2^j次方的最小值， 那么dp[i][j] = min(dp[i][j-1], dp[i+2^(j-1)][j-1]), 假设我们要查询l-r区间内的最小值那么我们可以将区间等分， 令k=log2(r-l+1), 答案就是min(dp[i][k], dp[j-2^k+1][k]),代码如下：
#include#include #include using namespace std;const int maxn = 1000 + 100;int a[1000 + 100], n;int dp[1000 + 100][30]; //以i开始长度为2^j的最小值int main() { scanf("%d", &n); for(int i=0; i
另外我们也可以使用线段数解决这类问题， 代码如下：测试题HDU1754 链接地址为 http://acm.hdu.edu.cn/showproblem.php?pid=1754
#include#include #include using namespace std;const int maxn = 200000 + 100;int n, m;int a[maxn];struct Segment{ int l, r; int num;}seg[3*maxn];void build(int rt, int l, int r){ //建树 seg[rt].l = l; seg[rt].r = r; if(l == r){ seg[rt].num = a[l]; }else{ int chl=2*rt, chr=2*rt+1; build(chl, l, (l+r)/2); build(chr, (l+r)/2+1, r); seg[rt].num = max(seg[2*rt].num, seg[2*rt+1].num); }}int query(int rt, int l, int r){ //查询l-r区间的最大值 if(seg[rt].l==l && seg[rt].r==r){ return seg[rt].num; } int mid = (seg[rt].l+seg[rt].r)/2; if(r<=mid) //l-r位于左区间 return query(2*rt, l, r); else if(l>mid) //l-r位于右区间 return query(2*rt+1, l, r); else { int v1 = query(2*rt, l, mid); int v2 = query(2*rt+1, mid+1, r); return max(v1, v2); }}void update(int rt, int i, int g){ //将同学i的成绩改为g if(seg[rt].l==i && seg[rt].r==i){ seg[rt].num = g; return ; } int mid = (seg[rt].l+seg[rt].r)/2; if(i <= mid) update(2*rt, i, g); else update(2*rt+1, i, g); seg[rt].num = max(seg[2*rt].num, seg[2*rt+1].num); //回溯时更新数组}int main() { while(scanf("%d%d", &n, &m) == 2){ for(int i=1; i<=n; i++) scanf("%d", &a[i]); build(1, 1, n); char str[10]; int l, r; for(int i=0; i