线段树合并 总结

今天学习了一下动态开点的线段树以及线段树合并吧

理解应该还是比较好理解的，动态开点的话可以避免许多空间的浪费，因为这类问题我们一般建立的是权值线段树，而权值一般范围比较大，直接像原来那样开四倍空间的话空间复杂度不能承受。

动态开点的代码如下：

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 
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 
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;
}

2.洛谷P3224

题意:

一开始给出$n$个点，$m$条边，每个点都有其权值，然后会不断地加边，中途可能会有询问，格式为"$v$ $k$"，意义为当前与$v$连通的所有点中，权值第$k$小的岛是哪座岛。

题解：

涉及到连通性，我们考虑用并查集来处理。具体做法为对于每个连通块建立一颗权值线段树来维护信息，然后对于加边过程，就不断合并两点所在集合的线段树就行了。

对于询问，直接在对应线段树中询问当前点所在集合第k小就行。

代码如下：

#include 
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m;
int v[N], f[N], rt[N], lc[N * 20], rc[N * 20], sum[N * 20], rk[N *20];
int T ;
int find(int x) {
    return f[x] == x ? f[x] : f[x] = find(f[x]) ;
}
void insert(int &i, int l, int r, int x) {
    if(r < l) return ;
    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) ;
    sum[i] = sum[lc[i]] + sum[rc[i]] ;
}
int merge(int x, int y, int l, int r) {
    if(!x) return y;
    if(!y) return x;
    if(l == r) {
        sum[x] += sum[y] ;
        return x;
    }
    int mid = (l + r) >> 1;
    lc[x] = merge(lc[x], lc[y], l, mid) ;
    rc[x] = merge(rc[x], rc[y], mid + 1, r) ;
    sum[x] = sum[lc[x]] + sum[rc[x]] ;
    return x;
}
int query(int root, int l, int r, int k) {
    if(l == r) return l ;
    int mid = (l + r) >> 1;
    if(sum[lc[root]] >= k) return query(lc[root], l, mid, k) ;
    else return query(rc[root], mid + 1 ,r ,k - sum[lc[root]]) ;
}
int main() {
    scanf("%d%d",&n, &m) ;
    for(int i = 1; i <= n; i++) scanf("%d", &v[i]), rk[v[i]] = i;
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= n; i++) insert(rt[i], 1, n, v[i]) ;
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d",&u, &v);
        int fx = find(u), fy = find(v) ;
        if(fx != fy) {
            rt[fx] = merge(rt[fx], rt[fy], 1, n) ;
            f[fy] = fx;
        }
    }
    int q ;
    scanf("%d", &q) ;
    char s[2] ;
    while(q--) {
        int u, v;
        scanf("%s%d%d",s, &u, &v);
        if(s[0] == 'Q') {
            int fx = find(u);
            if(sum[rt[fx]] < v) {
                printf("-1\n");
                continue ;
            }
            int ans = query(rt[fx], 1, n, v) ;
            printf("%d\n", rk[ans]);
        }else {
            int fx = find(u), fy = find(v) ;
            if(fx != fy) {
                rt[fx] = merge(rt[fx], rt[fy], 1, n) ;
                f[fy] = fx;
            }
        }
    }
    return 0;
}

3.洛谷P3521

题意：

给一棵n(1≤n≤200000个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。

题解：

假设当前点的左右儿子分别为$ls$，$rs$，很容易发现，交换以这两个结点为根节点的子树，并不会影响他们的祖宗交换时逆序对的个数。所以我们可以考虑每一层贪心地进行交换，此时局部最优即全局最优。

同时，对于区间$\left[L,R\right]$，设其中点为$mid$，我们只需要考虑这样的逆序对$\left(x,y\right)$，满足$L\leq x\leq mid$，$mid+1\leq y\leq R$即可，并不需要考虑在同一个子树中的逆序对数量。

由于这是权值线段树，那么逆序对其实很好统计，对于两颗线段树代表同一段区间的两个节点，考虑交换与不交换两种情况，分别取左、右部分或者右、左部分统计逆序对个数。最后取最小值就可以了。

详细见代码:

#include 
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n ;
ll sum[N * 22] ;
int lc[N * 22], rc[N * 22], rt[N * 22];
int T;
ll ans, sum1, sum2;
int merge(int x, int y) {
    if(!x) return y;
    if(!y) return x;
    sum[x] += sum[y] ;
    sum1 += sum[lc[x]] * sum[rc[y]] ;
    sum2 += sum[rc[x]] * sum[lc[y]] ;
    lc[x] = merge(lc[x], lc[y]) ;
    rc[x] = merge(rc[x], rc[y]) ;
    return x;
}
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) ;
    sum[i] = sum[lc[i]] + sum[rc[i]] ;
}
void dfs(int &p) {
    int x, ls, rs;p = 0;
    cin >> x ;
    if(x == 0) {
        dfs(ls);
        dfs(rs);
        sum1 = sum2 = 0;
        p = ls ;
        p = merge(ls, rs) ;
        ans += min(sum1, sum2) ;
    }
    else insert(rt[x], 1, n, x), p = rt[x];
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    int t = 0;
    dfs(t);
    cout << ans ;
    return 0 ;
}