ST表 C++

ST表是一种简洁、高效的数据结构，用于解决区间查询问题。它可以在O(log n)的时间复杂度内完成各种区间查询操作。

ST表的构建过程是基于动态规划的思想。首先，将原始数据按照固定长度划分为若干个区间，以每个区间的最小元素作为该区间的代表值。然后，根据代表值的特点，利用动态规划的方式计算出每个区间段的最小值。

构建好ST表后，可以进行各种区间查询操作，比如查询某个区间的最小值、最大值、平均值等。查询操作的时间复杂度为O(log n)，其中n为原始数据的长度。

ST表的优势在于它的查询效率高，并且不需要额外的存储空间。它可以应用于各种区间查询问题，如最小值查询、最大值查询、区间和查询等。

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define PA pair<int, int>
#define KUI ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int con = 2e5 + 4;
const int N = 2e5;
const int mod = 998244353;
int n, m, k, f[con][22];
void take()
{cin >> n;for (int i = 1; i <= n; i++){cin >> f[i][0];}for (int j = 1; j <= 20; j++){for (int i = 1; i + (1 << j) - 1 <= n; i++){f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}cin >> m;int l, r;while (m--){cin >> l >> r;int ans = log2(r - l + 1);cout << max(f[l][ans], f[r - (1 << ans) + 1][ans]) << endl;}
}
signed main()
{KUI;int t1 = 1;cin >> t1;while (t1--){take();}return 0;
}