一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最大值。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int res[10][4] = { 0 };//ST表的大小
void fillSTForm(int src[], int n, int res[][4])
{
int i, j;
for (i = 0; i < n; i++)
{
res[i][0] = src[i];
}
for (i = 1; (1<<i)<= n; i++)//1<<i相当于2^i,保证时间复杂度是log n
{
for (j = 0; j < n-(1 << i) + 1; j++)
{
res[j][i]= max(res[j][i-1],res[j+(1<<(i-1))][i-1]);
}
}
}
int searchSTData(int src[],int l,int r)//查表，取最大值
{
int n =log2( r - l + 1);//向下取整
return max(res[l][n], res[r - (1 << n) + 1][n]);
}
int main()
{
int a[10] = { 1, -5, 8, 3, -4, 7, 6, -1, 2, 9 };
fillSTForm(a, 10, res);//填表
cout<<searchSTData(a,2,6)<<endl;
/*for (int i = 0; i < 10; i++) //填表的输出
{
for (int j = 0; j < 4; j++)
{
cout << res[i][j]<< ' ';
}
cout << endl;
}*/
system("pause");
return 0;
}
