位運算
與& 或| 異或^ 左移<< 右移>>
\(x<<y=x·2^{y}\)
\(x>>y=\frac{x}{2^{y}}\)
\(2a+1=(a<<1)|1\)
\(a\)%\(2=a\)&\(1\)
st表
當st表合并的復雜度為\(O(1)\)時，st表構建的復雜度為\(O(nlogn)\),查詢的復雜度為\(O(1)\)，但是st表并不支持修改，
求區間最大值/最小值：復雜度\(O(n)\)
st表的核心在于倍增和DP，
\(f[i][j]\)表示以第\(i\)個數作為左端點，長度為\(2^{j}\)的區間的最值，也就是\([i,i+2^{j}-1]\)的區間最值，
\(f[i][0]=a[i]\)
\(f[i][j]=merge(f[i][j-1],f[i+2^{j-1}][j-1])\)
詢問一個區間\([l,r]\)的區間最值，
區間的極值就是兩個長度為\(2^{k}\)的子區間的極值，
設 $ k = \left \lfloor log ( r - l + 1 ) \right \rfloor $ ,那么，
\(ans=merge\{f[l][k],f[r-2^{k}+1][k]\}\)
merge函式表示資訊合并，詢問最大值時用max，詢問最小值時用min，
例題
【問題描述】
我們有一個n行m列的矩陣，
K次詢問矩陣矩陣最值，
注意
1、如果塊重疊對最后的答案有影響，那么不能使用st表處理，
2、呼叫一次cmath庫中的\(log_{2}\)函式時間復雜度是\(O(logn)\)的，我們可以預處理出Log陣列，
并非原創，僅是整理，請見諒
Lo問我為什么看星星，我覺得銀河和代碼是同一種東西，這也是一種回答，————Co轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/482109.html
標籤：C++
上一篇：SMFL 教程&個人筆記（2）