什么是倍增法？
?1,2,4,8,16,32，。。。。。
?每個數(shù)是前面的一倍
?步長翻倍
?ST（Sparse Table，稀疏表）表
–應用：解決RMQ問題
–RMQ（Range Minimum/Maximum Query），即區(qū)間最值查詢，是指這樣一個問題：對于長度為n的數(shù)列A，回答若干詢問RMQ（A,i,j）(i,j<=n)，返回數(shù)列A中下標在i，j之間的最小/大值。
?例如：
?A數(shù)列為：3 2 4 5 6 8 1 2 9 7
?F[1，0]表示第1個數(shù)起，長度為2^0=1的最大值，其實就是3這個數(shù)。
?同理 F[1,1] = max(3,2) = 3,
?F[1,2]=max(F[1,1],4,5)= 5，
?F[1,3]= max(F[1,2],6,8,1,2) = 8;
?F[1,4]=max(F[1,3],9,7)=9
[if ppt]?[endif]
?像上面的表，每個表的步長依次翻倍
?如果查詢整個區(qū)間最大的數(shù)值，直接計算
?F[1,4]=9
[if ppt]?[endif]
[if ppt]?[endif]
[if ppt]?[endif]
