详解请看https://blog.csdn.net/u013377068/article/details/79900343
#include<stdio.h>
#include<algorithm>
using namespace std;
const int INF = 100010;
void ST();
int RMQ(int i ,int j);
int dp[INF][20];
void ST()
{
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] = max(dp[i][j-1], dp[i + (1 << (j-1))][j-1]);
}
}
}
int RMQ(int i, int j)
{
if(i > j)
return 0;
int k = 0;
while((1<<(k + 1)) <= j -i +1)k++; // k 为log2(j - i + 1)
return max(dp[i][k], dp[j - (1 << k) + 1][k]);
}