本文共 1080 字，大约阅读时间需要 3 分钟。

解决什么问题：区间查询最值

倍增思想：每次得出结果的范围呈2的幂次增长，有人说相当于二分，目前我觉得相当于线段树的查找.

具体理解看代码：

/*倍增法求ST*/#include<math.h>#include<iostream>#include<stdio.h>#include<string.h>using namespace std;int main(){    int n,dp[110][110];    memset(dp,0,sizeof(dp));    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&dp[i][0]);    /*dp[i][j]=x  x就是[i,i+2^j-1]的最大值*/    for(int j=1;j<=log2(n);j++)/* 保证2 ^ j < = n */        for(int i=1;i<=n-(1<<j)+1;i++)/* i+2^j-1<=n -> i<=n-2^j+1 */            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);    /*对于所有点 i 由已知u [i,i+2^(j-1)-1] 范围内的最值求出他的二倍范围内的最值    for(int i=1;i<=n;i++)    {        printf("i=%d\n",i);        printf("dp[%d][0]:%d  ",i,dp[i][0]);        for(int j=1;j<=log2(n);j++)            if(dp[i][j])            printf("dp[%d][%d]=dp[%d][%d],dp[%d][%d]:%d   ",i,j,i,j-1,i+(1<<(j-1)),j-1,dp[i][j]);//i,i+2^j-1        printf("\n");    }    好像确实像二分多一点*/    int l,r,k;    scanf("%d%d",&l,&r);    k=log2(r-l+1);    /* 2^k 为从l开始的查询区间的长度,2^k<r-l+1 -> l<r-2^k+1 */    printf("%d\n",max(dp[l][k],dp[r-(1<<k)+1][k]));    return 0;}/*101 2 3 4 5 6 7 8 9 10*/