倍增与分治

ST表

可用于求解区间最大、最小值、GCD、LCM及满足相应性质的区间运算：算子满足区间可加性。

以求解区间最大值为例：

设\(ST_{i,j}\)表示从下标\(i\)开始的长度为\(2^i\)的区间最大值，初始化\(ST_{i,0}=a_i\)。

构建\(ST\)表时，有\(ST_{j,i}=\max(ST_{j,i-1},ST_{j+2^i-1,i-1})\)

求解询问\([L,R]\)时，计算区间\(k=\log_2\lfloor R-L+1\rfloor\)，\(ans=\max(ST_{L,k},ST_{R-2^k+1,k})\)

【倍增】Luogu P1890 区间GCD

给出序列\(A=\left \{a_1,a_2,\cdots,a_n \right \}\)与\(q\)个询问，每个询问包含\(L,R\)两个参数，求\(gcd(a_L,a_{L+1},\cdots,a_{R-1},a_R)\)

参考解答

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int lg[N],st[N][20],n,q,ans;
int gcd(int x,int y)
{
    if(!y) return x;
    return gcd(y,x%y); 
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&st[i][0]);
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    for(int j=1;j<=lg[n];j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
    int x,y;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        int len=lg[y-x+1];
        ans=gcd(st[x][len],st[y-(1<<len)+1][len]);
        printf("%d\n",ans);
    }
    return 0;
}