ST表模板

 ST表是离线算法，在O(nlogn)的时间复杂度内预处理后可以在O(1)的时间内查询[l,r]的最值

ST表的思路是用动态规划的思路预处理以第i个数为起点，长度为2^j的区间的最值；

dp方程为

区间最大值

#include
#define endl "n"
using namespace std;
const int inf=0x3f3f3f3f;
int t;
int n,m,k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    vector a(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    m=log2(n)+1;
    vector> st(n+1,vector(m,-inf)); //最大值
    for(int j=0;j>q;
    while(q--)
    {
        int l,r,k;
        cin>>l>>r;
        k=log2(r-l+1);
        cout< 
区间最小值
 

#include
#define endl "n"
using namespace std;
const int inf=0x3f3f3f3f;
int t;
int n,m,k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    vector a(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    m=log2(n)+1;
    vector> st(n+1,vector(m,inf)); //最小值
    for(int j=0;j>q;
    while(q--)
    {
        int l,r,k;
        cin>>l>>r;
        k=log2(r-l+1);
        cout< 
 ST表还可以结合其他离线数据结构如差分