今天学习了一下动态开点的线段树以及线段树合并吧
理解应该还是比较好理解的，动态开点的话可以避免许多空间的浪费，因为这类问题我们一般建立的是权值线段树，而权值一般范围比较大，直接像原来那样开四倍空间的话空间复杂度不能承受。
动态开点的代码如下：
void insert(int &i, int l, int r, int x) { i = ++T; if(l == r) { sum[i]++; return ; } int mid = (l + r) >> 1; if(x <= mid) insert(lc[i], l, mid, x) ; if(x > mid) insert(rc[i], mid + 1, r, x) ; update(i); }
因为对应位置的结点所代表的区间范围都是一样的，只是保存的信息有所不同，如果信息具有可加性，或者说区间信息可以合并的话，那么就可以两棵树同时往根节点开始同时往下递归遍历树：如果其中一个结点为空，那么我们就返回另外一个结点；否则，选一个结点作为合并之后的点，用另一个点来更新信息即可。最后自底向上维护我们需要的信息就好了。
合并代码如下：
int merge(int x, int y) { if(!x) return y; if(!y) return x; sum[x] += sum[y] ;//合并区间信息 lc[x] = merge(lc[x], lc[y]) ; rc[x] = merge(rc[x], rc[y]) ; return x;//相当于删除另外一个结点 }
假设我们以$n$个点为根建立权值线段树，由于我们是动态开点，每颗线段树最后都是一条链，那么空间复杂度和时间复杂度都是$O(nlogn)$的。最后我们合并的时候，每次merge操作都会减少一个点，所以最后总的合并过程时间复杂度为$O(nlogn)$，也是十分优秀的了。
接下来看几道例题吧~
1.洛谷P3605
题意：
给出一颗树，每个点都有一个权值，最后对于每个点，输出在它的子树中，有多少个点的权值比它大。
题解：
这是一个比较裸的题，由于权值数量关系是可以合并的，我们对于每一个点建立一颗权值线段树。之后从1号结点开始dfs，在回溯的过程中不断合并就行了。
对于每个点，查询一下目前的线段树中有多少权值比它大的就可以了。
详见代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 5; int p[N], a[N], ans[N] ; int tre[N * 20], lc[N * 20], rc[N * 20], rt[N]; int n, T; struct Edge{ int v, next ; }e[N]; int head[N], tot ; void adde(int u, int v) { e[tot].v = v; e[tot].next = head[u]; head[u] = tot++; } void insert(int &i, int l, int r, int x) { if(r < l) return ; i = ++T; if(l == r) { tre[i]++ ; return ; } int mid = (l + r) >> 1 ; if(x <= mid) insert(lc[i], l, mid, x) ; if(x > mid) insert(rc[i], mid + 1, r, x) ; tre[i] = tre[lc[i]] + tre[rc[i]] ; } int query(int root, int l, int r, int x) { if(!root) return 0; if(l >= x) return tre[root]; int ans = 0; int mid = (l + r) >> 1; if(mid >= x) ans += query(lc[root], l, mid, x) ; ans += query(rc[root], mid + 1, r, x) ; return ans ; } int merge(int x, int y) { if(!x) return y; if(!y) return x; lc[x] = merge(lc[x], lc[y]) ; rc[x] = merge(rc[x], rc[y]) ; tre[x] = tre[lc[x]] + tre[rc[x]] ; return x; } void dfs(int u) { for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v ; dfs(v) ; rt[u] = merge(rt[u], rt[v]) ; } ans[u] = query(rt[u], 1, n, a[u] + 1) ; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++) cin >> p[i] , a[i] = p[i]; sort(p + 1, p + n + 1); int D = unique(p + 1, p + n + 1) - p - 1; for(int i = 1; i <= n; i++) a[i] = lower_bound(p + 1, p + D + 1, a[i]) - p; memset(head, -1, sizeof(head)) ; for(int i = 2; i <= n; i++) { int x;cin >> x; adde(x, i) ; } for(int i = 1; i <= n; i++) insert(rt[i], 1, n, a[i]) ; dfs(1) ; for(int i = 1; i <= n; i++) cout << ans[i] << ‘\n‘; return 0; }
由于本题中子树的信息也具有可加性。这个题还可以用树状数组来做，记录一下进点的$tot1$，遍历完整颗子树后，查询现在的$tot2$，这里的$tot1$，$tot2$都为比当前结点权值大的个数，然后$tot2$ - $tot1$即为答案。
代码如下：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 5; int p[N], a[N], ans[N] ; int c[N]; int n, T; struct Edge{ int v, next ; }e[N]; int head[N], tot ; void adde(int u, int v) { e[tot].v = v; e[tot].next = head[u]; head[u] = tot++; } int lowbit(int x) { return x & (-x) ; } void update(int p, int v) { for(int i = p ; i < N; i += lowbit(i)) c[i] += v ; } int query(int p) { int ans = 0 ; for(int i = p ; i > 0 ; i -= lowbit(i)) ans += c[i] ; return ans ; } void dfs(int u) { update(a[u], 1); int sum1 = query(N - 1) - query(a[u]) ; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; dfs(v) ; } int sum2 = query(N - 1) - query(a[u]) ; ans[u] = sum2 - sum1 ; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++) cin >> p[i] , a[i] = p[i]; sort(p + 1, p + n + 1); int D = unique(p + 1, p + n + 1) - p - 1; for(int i = 1; i <= n; i++) a[i] = lower_bound(p + 1, p + D + 1, a[i]) - p; memset(head, -1, sizeof(head)) ; for(int i = 2; i <= n; i++) { int x;cin >> x; adde(x, i) ; } dfs(1) ; for(int i = 1; i <= n; i++) cout << ans[i] << ‘\n‘; return 0; }
原文：https://www.cnblogs.com/heyuhhh/p/10720600.html
