树链剖分基础入门 -- 强大的树上操纵数据结构

树链剖分

对树进行重新编号，使得能将任意一条路径，变为o(logn)段连续区间。

• 重儿子:子树中节点数最多的根节点是重儿子。
• 其余点为轻儿子
• 重边：重儿子与父节点的边。
• 重链：极大的重边构成的路径

重儿子放置到父节点的重链中

轻儿子放置到子节点的重链中

dfs序:优先遍历重儿子,即可保证重链上的所有的编号是连续的。

定理：树中任意一条路径都可以拆分为O(logn)条重链,即可拆分成O(logn)个连续区间。

算法流程:dfs标记重儿子，然后dfs2找到重链

时间复杂度:上界是logn。

#include
using namespace std;
#define ll long long
const int maxn=1e5+5;
#define il (id<<1)
#define ir il+1
ll w[maxn],nw[maxn];
int n,m;
int sz[maxn],fa[maxn],son[maxn],dep[maxn],top[maxn];
int nid[maxn],cnt;
struct tree
{
    int l,r;
    ll lz,sum;
}tr[maxn<<2];
vector<int>e[maxn];
void dfs1(int s,int father,int depth)
{
    dep[s]=depth;
    fa[s]=father;sz[s]=1;
    for(auto to:e[s])
    {
        if(to==father)continue;
        dfs1(to,s,depth+1);
        sz[s]+=sz[to];
        if(sz[to]>sz[son[s]])son[s]=to;
    }
}
void dfs2(int s,int t)//用来放重链的起点，根据定理重链的起点是轻链。
{
    nid[s]=++cnt,nw[cnt]=w[s],top[s]=t;
    if(!son[s])return ;//没有重链表示是叶子节点
    dfs2(son[s],t);
    for(auto to:e[s])//遍历轻儿子
    {
        if(to==fa[s]||to==son[s])continue;
        dfs2(to,to);
    }
}
void pushdown(int id)
{
    if(tr[id].lz!=0)
    {
        tr[il].lz+=tr[id].lz;tr[il].sum+=tr[id].lz*(tr[il].r-tr[il].l+1);
        tr[ir].lz+=tr[id].lz;tr[ir].sum+=tr[id].lz*(tr[ir].r-tr[ir].l+1);
        tr[id].lz=0;
    }
}
void pushup(int id)
{
    tr[id].sum=tr[il].sum+tr[ir].sum;
}
void build(int id,int l,int r)
{
    tr[id]={l,r,0,0};
    if(l==r)
    {
        tr[id].sum=nw[r];
        return ;
    }
    int mid=(l+r)>>1;
    build(il,l,mid);
    build(ir,mid+1,r);
    pushup(id);
}
void update(int id,int l,int r,ll y)
{
    if(tr[id].l>=l&&tr[id].r<=r)
    {
        tr[id].lz+=y;
        tr[id].sum+=(tr[id].r-tr[id].l+1)*y;
        return ;
    }
    pushdown(id);
    if(tr[il].r>=l)update(il,l,r,y);
    if(tr[ir].l<=r)update(ir,l,r,y);
    pushup(id);
}
ll querry(int id,int l,int r)
{
    if(tr[id].l>=l&&tr[id].r<=r)
    {
        return tr[id].sum;       
    }
    pushdown(id);
    ll ans=0;
    if(tr[il].r>=l)ans+=querry(il,l,r);
    if(tr[ir].l<=r)ans+=querry(ir,l,r);
    return ans;
}
void update_path(int u,int v,ll k)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,nid[top[u]],nid[u],k);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    update(1,nid[u],nid[v],k);
}
void update_tree(int u,ll k)
{
    update(1,nid[u],nid[u]+sz[u]-1,k);
}
ll querry_path(int u,int v)
{
    ll ans=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        ans+=querry(1,nid[top[u]],nid[u]);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    ans+=querry(1,nid[u],nid[v]);
    return ans;
}
ll querry_tree(int u)
{
    return querry(1,nid[u],nid[u]+sz[u]-1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1,-1,1);
    dfs2(1,1);
    build(1,1,n);
    int q;
	scanf("%d",&q);
    while(q--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int u,v,k;
            scanf("%d%d%d",&u,&v,&k);
            update_path(u,v,k);
        }
        else if(op==2)
        {
            int u,k;
            scanf("%d%d",&u,&k);
            update_tree(u,k);
        }
        else if(op==3)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            printf("%lld\n",querry_path(u,v));
        }
        else 
        {
            int u;
            scanf("%d",&u);
            printf("%lld\n",querry_tree(u));
        }
    }
    return 0;
}
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

例题 2022年杭电多校第二场1001