封装函数版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

template <typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
    int n;
    vector<vector<T>> st;
    F func;
 
    SparseTable(const vector<T>& a, const F& f) : func(f) {
        n=(int)a.size()-1;
        int max_log = __lg(n) +1;
        st.resize(max_log+1);
        st[0] = a;
        for (int j = 1; j <=max_log; j++) {
            st[j].resize(n+1);
            for (int i = 1; i+(1<<(j-1))<=n ; i++) {
                st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    T get(int l, int r) const {
       int len=__lg(r-l+1);
	return func(st[len][l],st[len][r-(1<<len)+1]);
    }
};
void solve(){
	int n,m;
       cin>>n>>m;
       vector<int>a(n+1,0);
       for(int i=1;i<=n;i++)cin>>a[i];
        SparseTable<int>qmx(a,[](int i,int j){return max(i,j);});
       for(int i=1;i<=m;i++){
       	int l,r;
       	cin>>l>>r;
       cout<<qmx.get(l,r)<<endl;
       }
}

简洁版：使用下划线lg库函数，优化cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//值域为1e6
int a[N];
int f[20][N];
void init(int n){
	for(int i=1;i<=n;i++)f[0][i]=a[i];
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n;i++){
			f[j][i]=min(f[j-1][i],f[j-1][i+(1<<(j-1))]);
		}
	}
}
int query(int l,int r){
	int len=__lg(r-l+1);
	return min(f[len][l],f[len][r-(1<<len)+1]);
	
}

初始版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int lg[N];
int f[N][M];
//查询区间最值
//预处理f数组
void init()
{
	lg[1]=0;
	for(int i=2;i<=N;i++)lg[i]=lg[i>>1]+1;//预处理对数数组
	//f数组的含义区间以i开头，长度为2的j次方的区间的最大值
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r)
{
    int len = r - l + 1;
    int k =lg[len];
//查询时找到不大于当前区间长度的最大的2次幂，不难想到2的k次方>=区间的长度的一半
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    init();

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}