线段树合并

以前一直以为像 treap 的 merge 一样的, 从来没写过
突然发现处理树上问题的复杂度不会证

概述

就是很朴素的递归合并

// x 和 y 是当前合并的两个节点号
int merge(int x, int y, int l, int r)
    {
    if (!x || !y) return x + y;
    if (l == r)
    {
        <DO SOMETHING>
        return x;
    }
    ch[x][0] = merge(ch[x][0], ch[y][0], l, mid);
    ch[x][1] = merge(ch[x][1], ch[y][1], mid + 1, r);
    update(x);
    return x;
    }

分析这段代码, 容易得到, 一次合并两棵线段树的复杂度即为这个函数经过的节点数, 也就是两棵线段树重合的节点数

那么有这样一个问题:
树上有点权, 你需要给每个点开一个线段树(动态开点), 来维护其子数内点权的信息

于是需要不断把儿子的线段树合并到自己, 那么这样的复杂度如何呢?

每个点都会加一条链, 所以这样只加入会有 \(n \log n\) 个点

然后每次合并两个重合的点, 那么其中一个之后都不回去访问他了, 相当于删去了这个点, 复杂度即为访问一次的复杂度 \(O(1)\)

显然最后不会删完所有加入的点, 所以复杂度是 \(O(n \log n)\)

CF600E Lomsat gelral

题意:
一棵树有颜色, 1 为根, 求出每个子数内数量最多的(可能并列最多)颜色的和(比如颜色 2, 3 最多, 和为 2 + 3)

Sol:
权值线段树统计区间中最多出现的次数, 以及所有出现这个次数的和

namespace SEG
{
    const int MAXLG = 18, MAXT = MAXN * MAXLG;
    int tot, root[MAXN];
    LL sum[MAXT];
    int cnt[MAXT], mx[MAXT], ch[MAXT][2];
#define mid ((l + r) >> 1)
#define ls (ch[now][0])
#define rs (ch[now][1])
    void update(int now)
    {
    if (mx[ls] == mx[rs]) sum[now] = sum[ls] + sum[rs], mx[now] = mx[ls];
    else if (mx[ls] < mx[rs]) sum[now] = sum[rs], mx[now] = mx[rs];
    else sum[now] = sum[ls], mx[now] = mx[ls];
    }
    void insert(int & now, int l, int r, int c)
    {
    if (!now) now = ++ tot;
    if (l == r) 
    {
        sum[now] = c;
        cnt[now] += 1;
        mx[now] = cnt[now];
        return ;
    }
    if (c <= mid) insert(ls, l, mid, c);
    else insert(rs, mid + 1, r, c);
    update(now);
    }
    int merge(int x, int y, int l, int r)
    {
    if (!x || !y) return x + y;
    if (l == r)
    {
        sum[x] = sum[y];
        cnt[x] += cnt[y];
        mx[x] = cnt[x];
        return x;
    }
    ch[x][0] = merge(ch[x][0], ch[y][0], l, mid);
    ch[x][1] = merge(ch[x][1], ch[y][1], mid + 1, r);
    update(x);
    return x;
    }
    void merge(int u, int v)
    {
    root[u] = merge(root[u], root[v], 1, n);
    }
    LL getmax(int u)
    {
    return sum[root[u]];
    }
#undef mid
#undef ls
#undef rs
}

LL ans[MAXN];
void DFS(int u, int fa)
{
    SEG::insert(SEG::root[u], 1, n, c[u]);
    for (int i = head[u]; i; i = adj[i].nex)
    {
    int v = adj[i].to;
    if (v == fa) continue;
    DFS(v, u);
    SEG::merge(u, v);
    }
    ans[u] = SEG::getmax(u);
}

int main()
{
    n = in();
    for (int i = 1; i <= n; ++ i) c[i] = in();
    for (int i = 1; i < n; ++ i) link(in(), in()); 
    DFS(1, 0);
    for (int i = 1; i <= n; ++ i) printf("%lld ", ans[i]);
    return 0;
}

线段树合并

原文：https://www.cnblogs.com/Kuonji/p/12033280.html