差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:wangzai_milk:线段树合并 [2020/06/01 23:31]
wzx27
+++ 2020-2021:teams:wangzai_milk:线段树合并 [2020/07/11 17:48] (当前版本)
zars19
@@ 行 12: / 行 12: @@
 ==== 简介 ====
-有些树型的题目会需要在一个结点维护一棵线段树，例如每次把 $u$到$v$ 的路径上的每个点内加一个元素 $k$，然后求每个节点中出现次数最多的数，这时可以在每个点开一棵权值线段树，树上差分之后在 $\text{dfs}$ 中不断合并父子节点代表的两棵线段树。
+有些树型的题目会需要在一个结点维护一棵线段树，例如每次把 $u$ 到 $v$ 的路径上的每个点内加一个元素 $k$，然后求每个节点中出现次数最多的数，这时可以在每个点开一棵权值线段树，树上差分之后在 $\text{dfs}$ 中不断合并父子节点代表的两棵线段树。
+{{:2020-2021:teams:wangzai_milk:线段树合并2.png?600|}}
 其中的关键步骤是**动态开点**和**线段树的合并操作**：
@@ 行 33: / 行 35: @@
 然后合并的操作主要基于两棵线段树具有相同的值域所以有相同的结构，那么递归的处理左右子树即可。
-大致过程如下：都从各自的根开始递归左右子树，如果有一个棵树的子树为空则返回另一棵树的子树（的编号），否则一直合并到叶子。
+例如在维护区间内数字个数时：都从各自的根开始递归左右子树，如果有一个棵树的子树为空则返回另一棵树的子树（的编号），否则一直合并到叶子。
+注：结点中的数字表示他的子树中有多少个数字，不是编号
 {{:2020-2021:teams:wangzai_milk:线段树合并.png?800|}}
@@ 行 53: / 行 57: @@
 </code>
 ==== 复杂度 ====
-空间复杂度比较要注意（因为涉及数组开多大QAQ），每次 $\text{update}$ 最多开 $logn$ 个点，所以一般开 $mlogn$ 的数组，$m$ 表示 $\text{update}$ 次数，$n$ 表示权值线段树的值域上限。
+空间复杂度比较要注意（因为涉及数组开多大QAQ），每次 $\text{update}$ 最多开 $\log n$ 个点，所以一般开 $m\log n$ 的数组，$m$ 表示 $\text{update}$ 次数，$n$ 表示权值线段树的值域上限。
-<del>时间复杂度的话就不会搞了</del>，主要开销在 $\text{merge}$ 操作上，两个树的公共点越多开销越大（这好像没办法算啊），但注意一点是如果在一颗树上合并了 $n-1$ 次那么这个复杂度不会比直接建一棵完整的线段树来得大。
+同空间复杂度，每次 $\text{update}$ 最多开 $\log n$ 个点，所以这里的时间复杂度是 $O(m\log n)$。而 $merge$ 的复杂度正比于叶子节点的个数，又因为 $m$ 次操作最多产生 $m$ 个叶子，所以最坏的情况就是合并了 $m$ 个叶子节点及其路径，每次合并都是 $\log n$ 级别的，所以这部分的复杂度也是 $O(m\log n)$ 的。
 ==== 例题 ====
@@ 行 63: / 行 67: @@
 显然是树上点差分，但是值域很大，可以在每个点建一棵权值线段树，然后合并即可，注意差分在 $\text{update}$ 上有常数 $4$，所以开数组要多乘以 $4$。
+<hidden code>
+<code cpp>
+#include<bits/stdc++.h>
+#define p_ pair<int,int>
+#define mp_ make_pair
+#define ll long long
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=a;i<=b;i++)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 1e5+5;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+int n,m,fa[maxn][35],dep[maxn],lg[maxn],X[maxn],Y[maxn],Z[maxn],mxz,ans[maxn],cnt,rt[maxn],idz[maxn];
+vector<int> g[maxn];
+struct node
+{
+    int lc,rc,mx,id;
+}tr[maxn*80];
+inline void dfs(int u,int f)
+{
+    dep[u]=dep[f]+1,fa[u][0]=f;
+    rep(i,1,lg[dep[u]]) fa[u][i]=fa[fa[u][i-1]][i-1];
+    for(int v:g[u])if(v!=f){
+        dfs(v,u);
+    }
+}
+inline int lca(int x,int y)
+{
+    if(dep[x]<dep[y])swap(x,y);
+    while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
+    if(x==y) return x;
+    for(int i=lg[dep[x]-1];i>=0;i--){
+        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
+    }
+    return fa[x][0];
+}
+inline void push_up(int id)
+{
+    int lc=tr[id].lc,rc=tr[id].rc;
+    if(tr[lc].mx>=tr[rc].mx) tr[id].mx=tr[lc].mx,tr[id].id=tr[lc].id;
+    else tr[id].mx=tr[rc].mx,tr[id].id=tr[rc].id;
+}
+void update(int &id,int l,int r,int pos,int v)
+{
+    if(!id) id=++cnt;
+    if(l==r){
+        tr[id].mx+=v;tr[id].id=l;return ;
+    }
+    int mid = (l+r)>>1;
+    if(pos<=mid) update(tr[id].lc,l,mid,pos,v);
+    else update(tr[id].rc,mid+1,r,pos,v);
+    push_up(id);
+}
+int mergE(int p,int q,int l,int r)
+{
+    if (!p) return q; if (!q) return p;
+    if(l==r){
+        tr[p].mx+=tr[q].mx;return p;
+    }
+    int mid = (l+r)>>1;
+    tr[p].lc = mergE(tr[p].lc,tr[q].lc,l,mid);
+    tr[p].rc = mergE(tr[p].rc,tr[q].rc,mid+1,r);
+    push_up(p);
+    return p;
+}
+void dfs2(int u,int f)
+{
+    for(int v:g[u])if(v!=f){
+        dfs2(v,u);
+        rt[u] = mergE(rt[u],rt[v],1,mxz);
+    }
+    if(tr[rt[u]].mx) ans[u] = tr[rt[u]].id;
+}
+int main()
+{
+    fastio();
+    cin>>n>>m;
+    rep(i,1,n) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
+    rep(i,1,n-1) {int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);}
+    dfs(1,0);
+    rep(i,1,m){
+        cin>>X[i]>>Y[i]>>Z[i];
+        idz[i] = Z[i];
+    }
+    sort(idz+1,idz+m+1);
+    mxz = unique(idz+1,idz+m+1)-idz-1;
+    rep(i,1,m){
+        int z = lower_bound(idz+1,idz+mxz+1,Z[i])-idz;
+        update(rt[X[i]],1,mxz,z,1);
+        update(rt[Y[i]],1,mxz,z,1);
+        int Lca = lca(X[i],Y[i]);
+        update(rt[Lca],1,mxz,z,-1);
+        update(rt[fa[Lca][0]],1,mxz,z,-1);
+    }
+    dfs2(1,0);
+    rep(i,1,n) cout<<idz[ans[i]]<<endl;
+    return 0;
+}
+</code>
+</hidden>
 [[https://www.luogu.com.cn/problem/P3605|P3605 [USACO17JAN]Promotion Counting P]]
@@ 行 72: / 行 183: @@
 [[https://www.luogu.com.cn/problem/P3224|P3224 HNOI2012]永无乡]]
-$n$ 个点，两个操作，一是连接两个点，二是求某个点和所有和他相连的点的第$k$小。
+$n$ 个点，两个操作，一是连接两个点，二是求某个点和所有和他相连的点的第 $k$ 小。
 第 $k$ 小也是权值线段树干的事儿，连接的操作用并查集维护。

CVBB ACM Team

用户工具

站点工具

差别

页面工具