DQS DQS

线段树合并学习笔记

in 算法,线段树&&树状数组,数据结构read (134) 文章转载请注明来源!

被Splay的启发式合并的坑爹常数坑了无数次之后决定学习一下新姿势…

一些证明

正确性前提:对于同样值域的权值线段树,它们的结构是相同的。
所以可以同时递归处理,合并两子树可以直接把两子树根节点信息合并。

复杂度证明:两个线段树合并时,如果一个为空则返回另一个。否则递归合并左右儿子。这种合并方法至少和一个个点插入一样快,所以是$O(nlogn)$。缺点是空间复杂度也是这么大,所以有可能被卡MLE。

功能

本质就是提供了两个权值线段树合并的功能。一定程度上能代替平衡树的启发式合并,并且好写跑得快。

例题

hdu6133

题意:给一棵树,每个点有点权。对于一个子树,设它的子树大小为k,则权值从小到大排序为$a_1,a_2,...,a_k$。对于每个子树,求$\sum x*a_{k-x+1}$的值。

对于这个式子,可以理解为:a_i一共贡献的次数是比它大的数的个数+1。
思考两个线段树合并的过程:对于一个节点,它的左右儿子为两个线段树的左右儿子的加和。那样对于线段树中的这个点,它的子树的答案即两儿子的子树的答案+跨两儿子的贡献。那么只需要考虑比左儿子中的值大的个数,然后全加起来。即左儿子的权值和*右儿子的子树大小。

注意处理多个相同值的情况:这种情况只有在递归到叶子时才发生,所以特判叶子,做个等差数列求和即可。

(然而我的代码MLE了…很气)

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 100001;
const LL INF = 1000000010;
const LL mod = 1000000007;
const int Dx[] = {0,1,0,-1};
const int Dy[] = {1,0,-1,0};

LL read()
{
    LL n = 0;
    char a = getchar();
    int flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}


int val[SZ],lsh[SZ];

namespace Seg
{
    struct segment
    {
        int lc,rc,sz;
        LL sum,ans;
    }tree[1670000];

    int Segsz = 0;
    int newnode()
    {
        int p = ++ Segsz;
        tree[p].lc = tree[p].rc = 0;
        tree[p].sz = tree[p].sum = tree[p].ans = 0;
        return p;
    }

    void update(int p)
    {
        tree[p].sz = tree[tree[p].lc].sz + tree[tree[p].rc].sz;
        tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
        tree[p].ans = tree[tree[p].lc].ans + tree[tree[p].rc].ans;
    }

    void insert(int &p,int l,int r,int x)
    {
        if(!p) p = newnode();
        if(l == r) { tree[p].sz = 1; tree[p].ans = tree[p].sum = lsh[x]; return ;}
        int mid = l + r >> 1;
        if(x <= mid) insert(tree[p].lc,l,mid,x);
        else insert(tree[p].rc,mid + 1,r,x);
        update(p);
    }
}
using namespace Seg;

int n,m;
vector<int> g[SZ];

int root[SZ];

int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    tree[x].lc = merge(tree[x].lc,tree[y].lc);
    tree[x].rc = merge(tree[x].rc,tree[y].rc);
    tree[x].sz += tree[y].sz; tree[x].sum += tree[y].sum;
    if(!tree[x].lc && !tree[x].rc) tree[x].ans = (tree[x].sz + 1) * tree[x].sum >> 1ll;
    else tree[x].ans = tree[tree[x].lc].ans + tree[tree[x].rc].ans + tree[tree[x].lc].sum * tree[tree[x].rc].sz;
    return x;
}

void dfs(int u,int f)
{
    int x = lower_bound(lsh + 1,lsh + 1 + m,val[u]) - lsh;
    insert(root[u],1,m,x);
    //cout << tree[root[u]].ans << endl;
    //for(int i = head[u];i;i = nxt[i])
    for(int i = 0;i < g[u].size();i ++)
    {
        int v = g[u][i];
        if(v == f) continue;
        dfs(v,u);
        root[u] = merge(root[u],root[v]);
    }
}

void init()
{
    Segsz = 0;
    for(int i = 0;i < 100001;i ++) root[i] = 0,g[i].clear();
    memset(tree,0,sizeof(tree));
}

int main()
{
    //freopen("in.txt","r",stdin); freopen("sb.txt","w",stdout);
    int T = read();
    while(T --)
    {
        init();
        n = read();
        for(int i = 1;i <= n;i ++) val[i] = read(),lsh[i] = val[i];
        sort(lsh + 1,lsh + 1 + n);
        m = unique(lsh + 1,lsh + 1 + n) - lsh - 1;

        for(int i = 1;i < n;i ++)
        {
            int x = read(),y = read();
            g[x].push_back(y);
            g[y].push_back(x);
        }
        dfs(1,0);
        for(int i = 1;i <= n;i ++)
            printf("%lld ",tree[root[i]].ans);
        puts("");
    }
    return 0;
}

bzoj2212

题意:给一个二叉树,每个叶子节点有点权,可以交换任意点的左右儿子。问任意次交换后遍历所形成的序列逆序对最少是多少。

考虑对于一个点两子树的交换:子树内部答案不变,只有跨两树的点对不一样。所以每次交换只需要考虑跨两树的点对使其最少即可。

将两子树的权值线段树合并,合并同时计算交换/不交换的逆序对数。然后取min即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<ctime>
#include<bitset>
#include<set>
#define x first
#define y second
using namespace std;

typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 5000010;
const LL INF = 1000000010;
const LL mod = 1000000007;
const int Dx[] = {0,1,0,-1};
const int Dy[] = {1,0,-1,0};


LL read()
{
    LL n = 0;
    char a = getchar();
    int flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

namespace Seg
{
    struct segment
    {
        int lc,rc;
        int sz;
    }tree[SZ];

    int Segsz = 0;
    int newnode() { return ++ Segsz; }

    void update(int p)
    {
        tree[p].sz = tree[tree[p].lc].sz + tree[tree[p].rc].sz;
    }

    void insert(int &p,int l,int r,int x)
    {
        if(!p) p = newnode();
        if(l == r) { tree[p].sz = 1; return ; }
        int mid = l + r >> 1;
        if(x <= mid) insert(tree[p].lc,l,mid,x);
        else insert(tree[p].rc,mid + 1,r,x);
        update(p);
    }

    void init() { Segsz = 0; }
}

using namespace Seg;

int n,m,totp;
int val[SZ],root[SZ],L[SZ],R[SZ];

void read_tree(int &p)
{
    if(!p) p = ++ totp;
    val[p] = read();
    if(!val[p])
        read_tree(L[p]),read_tree(R[p]);
}

LL cnt1,cnt2,ans = 0;

int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    cnt1 += (LL)tree[tree[x].lc].sz * tree[tree[y].rc].sz;
    cnt2 += (LL)tree[tree[x].rc].sz * tree[tree[y].lc].sz;
    tree[x].lc = merge(tree[x].lc,tree[y].lc);
    tree[x].rc = merge(tree[x].rc,tree[y].rc);
    update(x);
    return x;
}

void dfs(int u)
{
    if(!u) return ;
    dfs(L[u]); dfs(R[u]);
    if(!val[u])
    {
        cnt1 = 0,cnt2 = 0;
        root[u] = merge(root[L[u]],root[R[u]]);
        ans += min(cnt1,cnt2);
    }
}

int main()
{
    n = read();
    int rt = 0;
    read_tree(rt);
    for(int i = 1;i <= totp;i ++)
        if(val[i]) insert(root[i],1,n,val[i]);
    dfs(1);
    printf("%lld\n",ans);
    return 0;
}

bzoj4756

题意:一棵树,有点权。询问每个点的子树中有多少个点的权值比他大。

离散化后就是线段树合并裸题。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SZ = 2000010;
const int INF = 1e9 + 10;


LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int n,m;
int a[SZ],lsh[SZ],ans[SZ];

vector<int> g[SZ];

struct seg
{
    int lc,rc;
    int sz;
}tree[SZ];

int Segsz = 0;

void update(int p)
{
    tree[p].sz = tree[tree[p].lc].sz + tree[tree[p].rc].sz;
}

void insert(int &p,int l,int r,int x)
{
    if(!p) p = ++ Segsz;
    if(l == r) { tree[p].sz ++; return ; }
    int mid = l + r >> 1;
    if(x <= mid) insert(tree[p].lc,l,mid,x);
    else insert(tree[p].rc,mid + 1,r,x);
    update(p);
}

int ask(int p,int x)
{
    int ans = 0;
    int l = 1,r = m;
    while(l != r)
    {
        int mid = l + r >> 1;
        if(x <= mid) ans += tree[tree[p].rc].sz,p = tree[p].lc,r = mid;
        else p = tree[p].rc,l = mid + 1;
    }
    return ans;
}

int root[SZ];

int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    tree[x].lc = merge(tree[x].lc,tree[y].lc);
    tree[x].rc = merge(tree[x].rc,tree[y].rc);
    tree[x].sz += tree[y].sz;
    update(x);
    return x;
}

void dfs(int u)
{
    for(int i = 0;i < g[u].size();i ++)
    {
        int v = g[u][i];
        dfs(v);
        root[u] = merge(root[u],root[v]);
    }
    ans[u] = ask(root[u],a[u]);
    insert(root[u],1,m,a[u]);
}

int main()
{
    n = read();
    for(int i = 1;i <= n;i ++) lsh[i] = a[i] = read();
    sort(lsh + 1,lsh + 1 + n);
    m = unique(lsh + 1,lsh + 1 + n) - lsh - 1;
    for(int i = 1;i <= n;i ++) a[i] = lower_bound(lsh + 1,lsh + 1 + m,a[i]) - lsh;
    for(int i = 2;i <= n;i ++) g[read()].push_back(i);
    dfs(1);
    for(int i = 1;i <= n;i ++) printf("%d\n",ans[i]);
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法线段树&&树状数组数据结构
最后由DQS修改于2017-10-17 23:52
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆