ST表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。
常用于区间问题，如区间最值、区间最大公因数。
ST表的模板
ST表模板题
ST表 Oi Wiki
alt text
ST表可以用于解决可重复贡献问题，例如区间最值、区间最大公因数、区间按位与、区间按位或。核心思想是倍增法，覆盖的区间不会因为被覆盖而影响答案。 
核心代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| const int N = 1e5;
int st[N][20];
for(int i=1;i<=n;i++)cin>>st[i][0];
for(int j=1;j<20;j++)
{
for(int i=1;i<=n&&(i+(1<<(j-1)))<=n;i++)
{
st[i][j] = opt(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
}
int s = log2(r-l+1);
int ans = opt(st[l][s], st[r-+(1<<s)+1][s]);
|
RMQ区间最值问题
题意：有N个奶牛，Q次询问，问区间AB的最大值与最小值的差。
解题：两个ST表
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
| void solve()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>stmax[i][0];
stmin[i][0]=stmax[i][0];
}
for(int j=1;j<20;j++)
{
for(int i=1;i<=n&&(i+(1<<(j-1)))<=n;i++)
{
stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
}
}
int a,b;
while(q--)
{
cin>>a>>b;
int s=logn[b-a+1];
cout<<max(stmax[a][s],stmax[b-(1<<s)+1][s])-min(stmin[a][s],stmin[b-(1<<s)+1][s])<<endl;
}
}
void init()
{
logn[1]=0;
logn[2]=1;
for(int i=3;i<N;i++)logn[i]=logn[i/2]+1;
}
|
区间gcd问题
题目链接：CF475D
题意：有n组数q次询问，对于每一次询问x，数组能组成多少区间gcd使之等于x。
首先我们需要考虑一下多个数字的GCD的性质：对于一组数字的GCD，加入另外的一个数字组成的新数组，GCD只能变小或者不变。因此可以利用这个性质进行二分。
首先利用ST表预处理数组的区间GCD，复杂度为NlogN。之后我们以ai为起点，利用二分确定一段GCD没有发生改变的区间，则这段区间任意子区间的GCD都为这个值，可以用map记录一下。这个过程复杂度也为NlogN。最后q次询问，直接O1得出答案。
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
using namespace std;
const int N = 1e5+1;
void solve();
void init();
int logn[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int st[N][20];
int getst(int l,int r)
{
int s=logn[r-l+1];
return gcd(st[l][s],st[r+1-(1<<s)][s]);
}
void solve()
{
int n,q;
cin>>n;
for(int i=1;i<=n;i++)cin>>st[i][0];
for(int j=1;j<20;j++)
{
for(int i=1;i<=n&&(i+(1<<(j-1)))<=n;i++)
st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
mpi mp;
for(int i=1;i<=n;i++)
{
int cur=i;
while(cur<=n)
{
int val=getst(i,cur);
int l=cur, r=n;
while (l<r)
{
int mid=(l+r+1)>>1;
if (getst(i,mid)!=val)r=mid-1;
else l=mid;
}
mp[val]+=l-cur+1;
cur=l+1;
}
}
cin>>q;
int x;
while(q--)
{
cin>>x;
cout<<mp[x]<<endl;
}
}
void init()
{
logn[1]=0;
logn[2]=1;
for(int i=3;i<N;i++)logn[i]=logn[i/2]+1;
}
|
