ST表可以用来求区间最值，如果每次区间固定，可用单调队列来做。如果时间要求低，线段树也可以做。

1.建表

根据数据范围确定转移数组第一维的大小（就是看多少行可以推出来最值log2（N）），第二维数据范围，ST表对空间要求高，所以太大时可用vector

1.第一行枚举行数，len=log2(n)
2.第二行枚举每行对应倍增大小是n-(1<<i)+1,这里+1是要包含当前这一列的数。
3.状态转移，明显是从上一行转移而来，要么是当前这一列，要么是倍增后的(1<<i-1)

scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&dp[0][i]);//2的0次方即为原始数据
    //预处理
    len=log2(n);//倍增
    //枚举行数
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=n-(1<<i)+1;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<i-1)]);
            //printf("%d ",dp[i][j]);
        }
        //printf("\n");
    }

查询

关键是求出来哪一行，这一行的哪两个区间

1.len=log2(r-l+1)
2.区间1：l起点 区间2：r-(1<<len)+1 r一定为区间2的终点，那就推出起点，闭区间原因+1，向前移动倍增大小即可

while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        //由[l,r]区间求出第i行，找出这一行上的两个区间
        //求第几行
        len=log2(r-l+1);//对元素个数取log2()
        printf("%d\n",max(dp[len][l],dp[len][r-(1<<len)+1]));
    }

例题：

ST表

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,dp[20][N],len;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&dp[0][i]);//2的0次方即为原始数据
    //预处理
    len=log2(n);//倍增
    //枚举行数
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=n-(1<<i)+1;j++)
        {
            dp[i][j]=max(r-dp[i-1][j],dp[i-1][j+(1<<i-1)]);
            //printf("%d ",dp[i][j]);
        }
        //printf("\n");
    }
    //query
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        //由[l,r]区间求出第i行，找出这一行上的两个区间
        //求第几行
        len=log2(r-l+1);//对元素个数取log2()
        printf("%d\n",max(dp[len][l],dp[len][r-(1<<len)+1]));
    }

    return 0;
}

平衡队形

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[20][N],b[20][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[0][i]);
    b[0][i]=a[0][i];    
    }
    int len=log2(n);
    for(int i=1;i<=len;i++)
    for(int j=1;j<=n-(1<<i)+1;j++)
    {
    a[i][j]=max(a[i-1][j],a[i-1][j+(1<<i-1)]);
    b[i][j]=min(b[i-1][j],b[i-1][j+(1<<i-1)]);  
    }


    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int len=log2(r-l+1);
        int n1=max(a[len][l],a[len][r-(1<<len)+1]);
        int n2=min(b[len][l],b[len][r-(1<<len)+1]);
    printf("%d\n",n1-n2);
    }


    return 0;
}

求m区间内最小值

这道题正解应该用单调队列，线段树的做法还不会，ST表会mle或tle不过也算作暴力法吧

中国剩余定理

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=15;
int n,a[N],b[N],x,y;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    x=b[1],y=a[1];
    for(int i=2;i<=n;i++)
    {
        while((x%a[i])!=b[i])x+=y;
        y=lcm(y,a[i]);
    }
    cout<<x;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)solve();

    return 0;
}