ST算法

RMQ

d[i][k] 表示从i开始长度为$2^k$的区间的最值

复杂度$O(nlogn + q)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int d[maxn][maxl],LOG[maxn];

void init()
{
LOG[0] = -1;
for(int i=1;i<=n;++i)
{
LOG[i] = LOG[i/2] + 1;
d[i-1][0] = a[i-1];
}
for(int j=1;(1<<j)<=n;++j)
for(int i=0;i+(1<<(j-1)) -1<n;++i)
d[i][j] = min(d[i][j-1],d[i+(1<<(j-1))][j-1])
}

int query(int L,int R)
{
int t = LOG[R-L+1];
return min(d[L][t],d[R-(1<<t)+1][t]);
}

LCA

我们按dfs序来构建一个序列
比如
LCA

得到一个序列: 1,2,3,2,4,5,6

我们求lca(3,6) 即求 rmq_min(p(3),p(6)) = 2 p(i) 表示i第一次出现位置

由于一条边最多遍历两次,所以dfs序列最多可能有2(n-1)个元素,复杂度与RMQ一致

然而更常用的是与之类似的倍增算法
p[u][i] 记录的是u的第$2^i$层祖先
复杂度$O((n+q)log(n))$

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
int p[maxn][LOG]; //init -1
void dfs(int u,int fa,int dep = 1)
{
p[u][0] = fa;
deep[u] = dep;

for(int i=1;i<LOG;++i)
if(p[u][i-1] != -1)
p[u][i] = p[p[u][i-1]][i-1];

for(int i=0;i<G[u].size();++i)
{
int v = G[u][i];
if(v == fa) continue;
dfs(v,u,dep+1);
}
}

int query(int u,int v)
{
if(deep[u] < deep[v]) swap(u,v);
for(int i=LOG-1;i>=0;--i)
{
if(p[u][i]!=-1 && deep[p[u][i]] >= deep[v])
{
u = p[u][i];
}
}
if(u == v) return u;
for(int i=LOG-1;i>=0;--i)
{
if(p[u][i] != p[v][i])
{
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}