倍增，DFS序，欧拉序

Nannan Lv5
  2023-08-15 20:37 2023-08-15 20:37 Created   2024-09-30 19:50:24 2024-09-30 19:50:24 Updated      

倍增，DFS序，欧拉序

一、倍增

倍增的应用

①树上

回想一下之前学的倍增法求。是怎么求的呢？

对于是往上跳步可以到达的点

因为，所以一个节点的代的祖先是其代的祖先的的祖先.

即：

倍增表打好了，那怎么求呢？假设，第一步把，跳到同一个高度。如果跳到的还不是同一个点，那第二步就是一起往上跳。

②的级祖先

往上跳步

1
2
3
4
5
for(j = logn -> 0)
{
	if(k&(2^j))
			u = f[u][j]
}

举个栗子：

③记录路径信息(无修改)

预处理：

:往上跳步到达的点

:往上跳步经过的边的最小值

![image-20230710093641798](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710093641798.png)

查询：时间复杂度

例题:路径最小值 

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
#include<bits/stdc++.h>
using namespace std;
const int N = 201000;
const int LOGN = 18;
vector<pair<int,int>>edge[N];
int n,q;
int val[N][LOGN+1],f[N][LOGN+1],dep[N];

void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	for(auto i:edge[u])
	{
		int v = i.first;
		if(v==fa)continue;
		f[v][0] = u;
		val[v][0] = i.second;
		dfs(v,u);
	}
}


int query(int u,int v)
{
	int ans = 1<<30;
	if(dep[u]>dep[v])
		swap(u,v);
	int d = dep[v]-dep[u];
	for(int j = LOGN;j>=0;j--)
	{
		if(d&(1<<j))
		{
			ans = min(ans,val[v][j]);
			v = f[v][j];
		}
	}
	if(u==v)return ans;
	for(int j = LOGN;j>=0;j--)
	{
		if(f[u][j]!=f[v][j])
		{
			ans = min({ans,val[u][j],val[v][j]});
			u = f[u][j],v = f[v][j];
		}
	}
	ans = min({ans,val[u][0],val[v][0]});
	return ans;
}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	dfs(1,0);

	for(int j = 1;j<=LOGN;j++)
	{
		for(int u = 1;u<=n;u++)
		{
			f[u][j] = f[f[u][j-1]][j-1];
			val[u][j] = min(val[u][j-1],val[f[u][j-1]][j-1]);
		}
	}
	for(int i = 1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		cout<<query(u,v)<<endl;
	}
	return 0;
}

二、DFS序

性质：子树标号连续

![image-20230710105258087](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710105258087.png)

![image-20230710162136666](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710162136666.png)

子树编号连续=>子树问题—转化—>序列区间问题

比如：
单点修改，查询子树和—转化—>单点修改，查询区间和(树状数组)

查询根到x点路径和(类似深度)：怎么做呢？考虑对于每个点x，都在这个可以用差分实现

![image-20230710114307032](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710114307032.png)

例题

1.DFS序练习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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
int n,q;
const int N = 201000;
ll a[N];

vector<int>edge[N];
int l[N],r[N],tot;

template<class T>
struct BIT
{
	T c[N];
	int size;
	void init(int s){
		size = s;
		for(int i = 1;i<=size;i++)c[i] = 0;
	}
	T query(int x){//1...x
		assert(x<=size);
		T s = 0;
		for(;x;x-=x&(-x))
			s += c[x];
		return s;
	}
	void modify(int x,T s){//a[x]+=s
		assert(x!=0);//注意：树状数组下标不能是0，因为lowbit会死循环
		for(;x<=n;x+=x&(-x))
			c[x]+=s;
	}

};
BIT<ll>c1,c2;


void dfs(int u,int fa)
{
	l[u] = ++tot;
	for(auto v:edge[u])
	{
		if(v==fa)continue;
		dfs(v,u);
	}
	r[u] = tot;
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	c1.init(n),c2.init(n);
	dfs(1,0);
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		c1.modify(l[i],a[i]);
		c2.modify(l[i],a[i]);
		c2.modify(r[i]+1,-a[i]);
	}
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,y;
			cin>>x>>y;
			int d = y-a[x];
			a[x] = y;
			c1.modify(l[x],d);
			c2.modify(l[x],d);
			c2.modify(r[x]+1,-d);
		}
		else
		{
			int x;
			cin>>x;
			cout<<c1.query(r[x])-c1.query(l[x]-1)<<" ";
			cout<<c2.query(l[x])<<endl;
		}
	}
	return 0;
}

2.DFS序练习2

单点修改，子树查询，换根操作

换根：![image-20230710151424903](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710151424903.png)

难点：我们换根之后DFS序变了

那怎么办呢？

看起来是有换根操作，但实际上我们是不换根的，我们还是在原来的树的DFS序上做，拿一个变了记录根的位置。

  1. root = x:子树就是整棵树

    ![image-20230710105258087](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710105258087.png)

    ![image-20230710162124002](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710162124002.png)

  2. 根是x的子孙：&&,子树就是整棵树去掉这一段。

    这里为什么是：&&呢？

    解释：和是dfs的顺序，显然比先被dfs到，那就有，另一边是可以等于的，因为右端点可能一样，可参考上图。

    具体做法就是：从root开始倍增，如果深度比x大就往上跳，这样就能刚好跳到x的下面。更优的做法是在x儿子里面二分出l[root]在哪个区间里面，找到一个左端点<=它，右端点>=它的。

![image-20230710152425595](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230710152425595.png)

  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
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
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64;
int n,q;
const int N = 201000;
ll a[N];

vector<int>edge[N];
int l[N],r[N],tot;
vector<pair<int,int>>son[N];
template<class T>
struct BIT
{
	T c[N];
	int size;
	void init(int s){
		size = s;
		for(int i = 1;i<=size;i++)c[i] = 0;
	}
	T query(int x){//1...x
		assert(x<=size);
		T s = 0;
		for(;x;x-=x&(-x))
			s += c[x];
		return s;
	}
	void modify(int x,T s){//a[x]+=s
		assert(x!=0);//注意：树状数组下标不能是0，因为lowbit会死循环
		for(;x<=n;x+=x&(-x))
			c[x]+=s;
	}

};
BIT<ll>c1;


void dfs(int u,int fa)
{
	l[u] = ++tot;
	for(auto v:edge[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		son[u].push_back({l[v],r[v]});
	}
	r[u] = tot;
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	int root = 1;
	c1.init(n);
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		c1.modify(l[i],a[i]);
	}
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,y;
			cin>>x>>y;
			int d = y-a[x];
			a[x] = y;
			c1.modify(l[x],d);
		}
		else if(op==3)
		{
			cin>>root;
		}
		else
		{
			int x;
			cin>>x;
			if(x==root)
				cout<<c1.query(n)<<endl;
			else if(l[x]<l[root]&&r[x]>=r[root])
			{
				//二分出l[root]在哪个区间里面，找到一个左端点<=它，右端点>=它的
				auto seg = *prev(upper_bound(son[x].begin(), son[x].end(),pair<int,int>{l[root],r[root]}));//找到第一个<=l[root]的
				cout<<c1.query(n)-(c1.query(seg.second)-c1.query(seg.first-1))<<endl;
			}
			else
			{
				cout<<c1.query(r[x])-c1.query(l[x]-1)<<endl;
			}
		}
	}
	return 0;
}

3.DFS序+奇偶性分层+线段树

Problem - 383C - Codeforces

题意：给一颗n个节点的树，每个节点有点权，编号为1的节点是树的根。
有m次操作：
操作1：给x加上val，然后给x的所有子节点加上-val，x的子节点的子节点加上-(-val)，不断传递。
操作2：查询点x的点权。

思路：

该题是关于子树的问题，可以先将树转化为dfs序，变成序列问题再用线段树解决。

本题难点在于，每次下传val的时候，要取反。

我们设d[x]为x到根的奇偶性,0/1表示。

在修改x的点权时，在以x为根的子树中，所有与x深度奇偶性相同的点+val，所有与x深度奇偶性不同的点-val。

根据上述分析，我们考虑把奇数层和偶数层分开，建2棵树。

在修改x的时候，与x奇偶性相同的树[L,R]添加val，这样做是为了将[L,R]中与x奇偶性相同的点全部加上val
并且与x奇偶性不同的树[L,R]减少val，这样做是为了将[L,R]中与x奇偶性不同的点全部加上val

奇数树中，深度为偶数的位置是没用的，直接忽略，偶数树同理。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];
vector<int>edge[N];
int l[N],r[N],tot,d[N];
struct node
{
	ll t;
};

struct SegmentTree
{
	node seg[N*4];
	void settag(int id,ll t)
	{
		seg[id].val = seg[id].val+t;
		seg[id].t = seg[id].t + t;
	}

	void pushdown(int id)
	{
		if(seg[id].t!=0)
		{
			settag(id*2,seg[id].t);
			settag(id*2+1,seg[id].t);
			seg[id].t = 0;
		}
	}

	void modify(int id,int l,int r,int x,int y,ll t)
	{
		if(l==x&&r==y)
		{
			settag(id,t);
			return;
		}
		int mid = (l+r)/2;
		pushdown(id);
		if(y<=mid) modify(id*2,l,mid,x,y,t);
		else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
		else{
			modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
		}
	}

	ll query(int id,int l,int r,int x,int y)
	{
		if(l==x&&r==y)return seg[id].val; 
		int mid = (l+r)/2;
		pushdown(id);
		if(y<=mid)return query(id*2,l,mid,x,y);
		else if(x>mid)return query(id*2+1,mid+1,r,x,y);
		else{
			return max(query(id*2,l,mid,x,mid),query(id*2+1,mid+1,r,mid+1,y));
		}
	}

}T[2];


void dfs(int u,int fa,int dep)
{
	l[u] = ++tot;
	d[u] = dep;
	for(auto v:edge[u])
	{ 
		if(v==fa)continue;
		dfs(v,u,dep^1);
	}
	r[u] = tot;
}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	for(int i = 1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0,0);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,val;
			cin>>x>>val;
			T[d[x]].modify(1,1,n,l[x],r[x],val);
			T[d[x]^1].modify(1,1,n,l[x],r[x],-val);
		}
		else
		{
			int x;
			cin>>x;
			int ans = a[x]+T[d[x]].query(1,1,n,l[x],l[x]);
			cout<<ans<<endl;
		}
	}
	return 0;
}

三、欧拉序

![image-20230717082804260](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230717082804260.png)

根据欧拉序，求和的就是求和之间深度最小的点。转化位一个问题，用表写。

例题:树上LCA3 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10;

unsigned int A, B, C;
int n,m,tot,dep[N],p[N];
pair<int,int>f[22][N*2];
vector<int>edge[N];
ll ans = 0;
struct S_T {
    // op 函数需要支持两个可以重叠的区间进行合并
    // 例如 min、 max、 gcd、 lcm 等
    int  lg[N*2];
    void build(int n) {
        lg[0] = -1;

        for (int i = 1; i <= n; ++i) {
            lg[i] = lg[i / 2] + 1;
        }

        for (int i = 1; i <= 20; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
    }
    int query(int l, int r) {
        int len = lg[r - l + 1];
        return min(f[len][l], f[len][r - (1 << len) + 1]).second;
    }
} ST;



inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}

void dfs(int u,int fa)
{
    p[u] = ++ tot;
    dep[u] = dep[fa]+1;
    f[0][tot] = {dep[u],u};
    for(auto v:edge[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        f[0][++tot]={dep[u],u};
    }
}



int main(){
    scanf("%d%d%u%u%u", &n, &m, &A, &B, &C);
    // 输入树边
    for(int i = 1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1,0);
    ST.build(tot);
    for (int i = 1; i <= m; i++) {
        int l = p[rng61() % n + 1],r = p[rng61() % n + 1];
        if(l>r)swap(l,r);
        int d = ST.query(l,r);
        ans ^= 1ll*i*d;
    }
    cout<<ans<<"\n";
}

四、总结

  1. 倍增：无修改路径信息
  2. DFS序：待修改子树信息(转化为区间)，修改路径信息不行的(需要树链剖分)
  3. 欧拉序：LCA
  • Title: 倍增，DFS序，欧拉序
  • Author: Nannan
  • Created at : 2023-08-15 20:37:00
  • Updated at : 2024-09-30 19:50:24
  • Link: https://redefine.ohevan.com/2023/08/15/六、倍增，DFS序，欧拉序/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
倍增，DFS序，欧拉序
  1. 倍增，DFS序，欧拉序
    1. 一、倍增
      1. 倍增的应用
      2. ①树上
      3. ②的级祖先
      4. ③记录路径信息(无修改)
      5. 例题:路径最小值
    2. 二、DFS序
      1. 性质：子树标号连续
      2. 例题
      3. 1.DFS序练习1
      4. 2.DFS序练习2
      5. 3.DFS序+奇偶性分层+线段树
    3. 三、欧拉序
      1. 例题:树上LCA3
    4. 四、总结