线段树合并

佚名 6年前 (2019-04-23) 随笔 616人围观抢沙发百度已收录

线段树合并说全来就是动态开点权值线段树合并。所以你需要掌握权值线段树的基本知识以及知道什么是动态开点（雾

线段树合并的主要方式如下：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

对于两棵线段树都有的节点，新的线段树的该节点值为两者和。

对于某一棵线段树有的节点，新的线段树保存该节点的值。

然后对左右子树递归处理。

不能理解？那就看一下代码。

int merge (int l, int r, int u, int v)
{
    if (!u || !v) return u|v;
    if (l==r) {return val[++tot]=val[u]+val[v], tot;}
    int mid=l+r>>1, node=++tot;
    //若干操作
    ls[node]=merge(l, mid, ls[u], ls[v]);
    rs[node]=merge(mid+1, r, rs[u], rs[v]);
    val[node]=val[ls[node]]+val[rs[node]];
    return node;
}

看起来很暴力？那么复杂度是多少？

合并的复杂度显然与两棵线段树重合的叶子结点个数有关，实际上若叶子个数为\(m\)，那么一次合并的复杂度就是\(mlogn\)了。

我要合并\(n\)次怎么办？复杂度\(O(nmlogn)\)？

其实是\(O(nlogn)\)，可是我不会证。引用洛谷日报的证明：

来证明一下：
假设我们会加入\(k\)个点，由上面的结论，我们可以推出最多要新增\(klogk\)个点。
而正如我们所知，每次合并两棵线段树同位置的点，就会少掉一个点，复杂度为\(O(1)\) ，总共\(O(klogk)\)个点，全部合并的复杂度就是\(O(klogk)\)

例题：POI2011 ROT-Tree Rotations

给出一棵\(n\)个叶子的二叉树，仅叶子有点权，求通过变换任意几个点的左右子树使得前序遍历叶子的逆序对最小值。

\(dfs\)整棵树，对于一个节点，交换子树使逆序对更少则交换。如何求逆序对？线段树合并即可。

不过该题需要注意写法，不能每次合并到新开的节点，而应直接将线段树\(a\)合并到线段树\(b\)上，不然会\(MLE\)。

#include<cstdio>
#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)
#define per(i, a, b) for (register int i=(a); i>=(b); --i)
using namespace std;
const int N=6000005;
long long min(long long a, long long b){return a<b?a:b;}
int ls[N], rs[N], val[N], n, tot;
long long ans, ans1, ans2;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

int New(int l, int r, int x)
{
    val[++tot]=1;
    if (l==r) return tot;
    int mid=l+r>>1, node=tot;
    if (x<=mid) ls[node]=New(l, mid, x);
        else rs[node]=New(mid+1, r, x);
    return node;
}

int merge(int l, int r, int u, int v)
{
    if (!u || !v) return u+v;
    if (l==r) {val[u]=val[u]+val[v]; return u;}
    int mid=(l+r)>>1, node=u;
    ans1+=1ll*val[rs[u]]*val[ls[v]]; 
    ans2+=1ll*val[ls[u]]*val[rs[v]];
    ls[node]=merge(l, mid, ls[u], ls[v]);
    rs[node]=merge(mid+1, r, rs[u], rs[v]);
    val[node]=val[ls[node]]+val[rs[node]];
    return node;
}

int dfs()
{
    int v=read();
    if (v) return New(1, n, v);
    int node=merge(1, n, dfs(), dfs());
    ans+=min(ans1, ans2); ans1=ans2=0;
    return node;
}

int main()
{
    n=read(); dfs(); printf("%lld\n", ans);
    return 0;
}

后期有例题还会更的\(QAQ\)