ST表--倍增区间DP处理RMQ

只看该作者 · 2023-4-21 23:38

一.简单介绍
预处理：
①区间DP 转移方程 f[i][j] = max(f[i][j - 1],f[i + ][j - 1]) f[i][j]表示从i位置开始的后2^j个数中的最大值

这里分成两半，一半是即 ~ 和 ~

②不过区间在增加时，每次并不是增加一个长度，而是基于倍增思想，用二进制右移，每次增加2^i个长度，最多增加logn次

这样预处理了所有2的幂次的小区间的最值

（其实快速幂是倍增法很好的例子）

只看该作者 · 2023-4-21 23:38

查询：
③对于每个区间，分成两段长度为的区间，再取个最值

（这里的两个区间是可以有交集的，因为重复区间并不影响最值)

比如3,4,6,5,3一种分成3,4,6和6,5,3，另一种分成3,4,6和5,3，最大值都是6，没影响。

④所以O(nlogn)预处理，O(1)查询最值但不支持修改

只看该作者 · 2023-4-21 23:38

二.代码介绍
①预处理外层for上界:求到n最少需要加上2的k次方,即写成k=log2(n)

然后注意先换底公式（经qq提醒，或可直接用log2函数），然后转换成double，最后应取下界（即取int）防溢出

只看该作者 · 2023-4-21 23:38

②初始化f[i][0]=a[i]: 即 j=0显然区间[i,i]里只有它一个数

只看该作者 · 2023-4-21 23:38

③预处理两层for：外层j内层i，把j放外面，因为上界由i和j共同决定，而且区间长度由j决定，保证dp从小区间合并为大区间

注意内层循环，区间右端点下标为i+2^j-1，-1别漏

只看该作者 · 2023-4-21 23:39

④预处理 f[i][j] = max(f[i][j - 1],f[i + 2^(j - 1)][j - 1]) 或者·min

只看该作者 · 2023-4-21 23:39

⑤查询划分点：

左区间右端点2^p：求l到r最少需要加上2的p次方,即写成p=log2(r-l+1)，后面同①

右区间左端点k ：证明： [k][k+-1]<=>[k][r] k=r-2^p+1 因为p与区间长度有关，有时用len数组预处理某区间长度的k值

注意查询的l和r之间区间长度不一定刚好是2的次方，比如下图l,r，让区间重叠是没问题的

只看该作者 · 2023-4-21 23:39

⑥取两个区间最值的最值

只看该作者 · 2023-4-21 23:40

三.模板 P3865
①P3865 部分参考ttoj

复制

#include <bits/stdc++.h>

using namespace std;

#define N 500010   

int maxl[N][16], minl[N][16]; 

int  a[N];

int n,m;

void S_table(){

    int l = int(log((double)n)/log(2.0));

    for (int j=1;j<=l;j++){

        for (int i=1; i + (1 << (j-1) ) - 1 <=n;++i){

            maxl[i][j] = max(maxl[i][j-1], maxl[i + (1 << (j-1) )][j-1]);

            minl[i][j] = min(minl[i][j-1], minl[i + (1 << (j-1) )][j-1]);

        }

    }

}

int rmq(int l, int r){

    int k = int(log((double)(r-l+1))/log(2.0));

    int a1 = max(maxl[l][k], maxl[r - (1<<k) + 1][k]);

    int a2 = min(minl[l][k], minl[r - (1<<k) + 1][k]);

    return a1;

    //printf("Max: %d Min: %d\n", a1, a2);

}

 

 

int main()

{

        int x,y;

        cin>>n>>m; 

   for (int i=1;i<=n;++i)

    {

    scanf("%d", &a[i]);

    maxl[i][0] = minl[i][0] = a[i];

    }

    S_table();

    while(m--)

    {

            scanf("%d %d",&x,&y);

            printf("%d\n",rmq(x, y));

        }

   

}

只看该作者 · 2023-4-21 23:40

②poj 3264 裸题，最大-最小

复制

#include <iostream>

#include<algorithm>

#include<stdio.h>

#include<cmath>

using namespace std;

#define N 500010   

int maxl[N][16], minl[N][16]; 

int  a[N];

int n,m;

void S_table(){

    int l = int(log((double)n)/log(2.0));

    for (int j=1;j<=l;j++){

        for (int i=1; i + (1 << (j-1) ) - 1 <=n;++i){

            maxl[i][j] = max(maxl[i][j-1], maxl[i + (1 << (j-1) )][j-1]);

            minl[i][j] = min(minl[i][j-1], minl[i + (1 << (j-1) )][j-1]);

        }

    }

}

int rmq(int l, int r){

    int k = int(log((double)(r-l+1))/log(2.0));

    int a1 = max(maxl[l][k], maxl[r - (1<<k) + 1][k]);

    int a2 = min(minl[l][k], minl[r - (1<<k) + 1][k]);

    return a1-a2;

    //printf("Max: %d Min: %d\n", a1, a2);

}

 

 

int main()

{

        int x,y;

        cin>>n>>m; 

   for (int i=1;i<=n;++i)

    {

    scanf("%d", &a[i]);

    maxl[i][0] = minl[i][0] = a[i];

    }

    S_table();

    while(m--)

    {

            scanf("%d %d",&x,&y);

            printf("%d\n",rmq(x, y));

        }

   

}

只看该作者 · 2023-4-21 23:40

③华工校赛

区间gcd题解代码（gcd类似最值的性质）

复制

#include<bits/stdc++.h>

 

using namespace std;

 

#define mem(a,b) memset(a,b,sizeof(a))

#define REP(i,a,b) for(int i=a; i<=b; ++i)

#define PER(i,a,b) for(int i=a; i>=b; --i)

#define MP make_pair

#define PB push_back

#define fi first

#define se second

typedef long long LL;

typedef double DB;

 

const int maxn = 5e5;

const int Step = 17;

const int P = 1e9+7;

 

LL Gcd(LL a, LL b) { return b ? Gcd(b,a%b) : a; }

 

int n, ai[maxn+5];

int st[maxn+5][Step+2];

 

int len[maxn+5];

 

int Que(int l, int r) {

    int k = len[r-l+1];

    return Gcd( st[l][k], st[r-(1<<k)+1][k] );

}

 

int main() {

    scanf("%d", &n);

    REP(i,1,n) scanf("%d", ai+i), st[i][0] = ai[i];

    for(int k = 1; (1<<k) <= n; ++k) {

        for(int i = 1; i+(1<<k)-1 <= n; ++i) {

            st[i][k] = Gcd(st[i][k-1], st[i+(1<<(k-1))][k-1]);

        }

    }

    for(int i = 1; i <= n; ++i) {

        len[i] = len[i-1];

        if((1<<(len[i]+1)) < i) ++len[i];

    }

    LL ans = 0;

    REP(i,1,n) {

        int now = 0;

        for(int k = i, nx; k <= n; k = nx+1) {

            now = Gcd(now, ai[k]);

            int l = k+1, r = n;

            nx = k;

            while(l<=r) {

                int mid = (l+r)>>1;

                int tmp = Que(k,mid);

                if(tmp%now==0) nx = mid, l = mid+1;

                else r = mid-1;

            }

            ans = (ans + LL(nx-k+1) * now) % P;

        }

    }

    printf("%lld\n", ans);

    return 0;

}