ST表
1 // 区间最值问题的ST算法 2 void ST_prework() { 3 for (int i = 1; i <= n; i++) f[i][0] = a[i]; 4 int t = log(n) / log(2) + 1; 5 for (int j = 1; j < t; j++) 6 for (int i = 1; i <= n - (1<<j) + 1; i++) 7 f[i][j] = max(f[i][j-1], f[i + (1<<(j-1))][j-1]); 8 } 9 10 int ST_query(int l, int r) { 11 int k = log(r - l + 1) / log(2); 12 return max(f[l][k], f[r - (1<<k) + 1][k]); 13 }
对于只考虑首位状态的DP，考虑用倍增优化