算法学习ST表稀疏表解决RMQ问题

/*
&＃64;theme:ST表&＃xff08;sparse table&＃xff09;稀疏表
&＃64;writer:pprp
&＃64;declare:用动态规划的思想来解决RMQ问题&＃xff1b;
&＃64;date:2017/8/26
*//*方程
F[i,j]:区间[i,i &＃43; 2^j - 1]的最小值&＃xff0c;此时区间长度为2^j
转移方程&＃xff1a;F[i,j] &＃61; min(F[i,j - 1],F[i &＃43; 2^(j - 1),j - 1])
初始化&＃xff1a;F[i,0] &＃61; nArr[i];
*/#include using namespace std;int F[1000000][20];//待比较元素的个数最大为1百万void SparseTable(int a[], int len)
{//初始化for(int i &＃61; 0 ; i )F[i][0] &＃61; a[i];//递推//找到j的范围log2(n)int nlog &＃61; int(log(double(len))/log(2.0));for(int j &＃61; 1 ; j <&＃61; nlog; j&＃43;&＃43;){for(int i &＃61; 0 ; i ){//区间右端点不能超过数组最后一位下标if((i &＃43; (1 <1) < len ){F[i][j] &＃61; min(F[i][j - 1],F[i &＃43; (1 <<(j - 1))][j - 1]);}}}
}int RMQ(int a[], int len, int Start, int End)
{//中间变量的选取log2(len)int nlog &＃61; (int)(log(double(End-Start&＃43;1))/log(2.0));return min(F[Start][nlog], F[End - (1 <1][nlog]);
}int main()
{int a[] &＃61; {2,34,2,3,23,2,23,1,23,123,23,232,3,25,565,76};for(int i &＃61; 0 ; i <16 ; i&＃43;&＃43;){cout <" ";}cout << endl;SparseTable(a,16);int l, r;while(cin >> l >> r){cout <16,l,r) << endl;}return 0;
}

#include using namespace std;int F[1000000][20];
void ST(int a[],int len)
{for(int i &＃61; 0 ; i )F[i][0] &＃61; a[i];int nlog &＃61; int(log(double(len))/log(2.0));for(int j &＃61; 1; j <&＃61; nlog; j&＃43;&＃43;){for(int i &＃61; 0 ; i ){if(i&＃43;(1<1 < len)F[i][j] &＃61; max(F[i][j-1],F[i&＃43;(1<<(j-1))][j-1]);}}
}int RMQ(int a[],int len, int l, int r)
{int nlog &＃61; floor(log(double(r-l&＃43;1))/log(2.0));return max((F[l][nlog]),F[r-(1<1][nlog]);
}int main()
{int a[10000];int n;cin >> n;for(int i &＃61; 0 ; i )cin >> a[i];ST(a,n);int l,r;int cas;cin >> cas;while(cas--){cin >> l >> r;cout < endl;}return 0;
}