目录

 ST表部分的代码：

使用示范：

1.原理是“倍增”，直到两个长度为1的就可以合成一个长度为2的，两个2合成4，两个4合成8。

2.最后使用时没必要追求“正好匹配”，可以在范围内取多点：

比如看4~8长度为5（45678），我们取长度为4，看4~7与5~8的最大值哪个更大即可。

 ST表部分的代码：

//ST表vector<vector<int>>st(30,vector<int>(n+1));//len = 2的i次方int len = 1;for (int pow = 0; len <= n; pow++, len *=2){for (int left = 1; left <= n- len+1; left++){if (pow == 0)st[0][left] = arr[left];else{st[pow][left] = max(st[pow - 1][left], st[pow - 1][min(left + len / 2,n)]);}}}

使用示范：

void solve()
{int n, m;cin >> n >> m;vector<int>arr(n+1);for (int i = 1; i <= n; i++){cin >> arr[i];}//ST表vector<vector<int>>st(30,vector<int>(n+1));//len = 2的i次方int len = 1;for (int pow = 0; len <= n; pow++, len *=2){for (int left = 1; left <= n- len+1; left++){if (pow == 0)st[0][left] = arr[left];else{st[pow][left] = max(st[pow - 1][left], st[pow - 1][min(left + len / 2,n)]);}}}for (int i = 1; i <= m; i++){int l, r;cin >> l >> r;//l+len-1<=r	len = 2的k次方//len <= r-l+1//k <= log(r-l+1);int k = log2(r - l + 1);cout << max(st[k][l], st[k][r-pow(2,k)+1]) << endl;}
}