值域有交平衡树合并及复杂度证明

值域有交平衡树合并及复杂度证明

以下内容理论上对多种平衡树都成立，但是此处假设这个只是对 FHQ Treap 成立。

合并

对于两棵树 l,rl,r ，设 ll 树根的优先级大于 rr ，那么先判断他们值域是否有交，如果没有交那么直接用 FHQ 的合并就行。如果有交就按照 ll 的权值将 rr 分裂后将 ll 的两个儿子分别和分裂出来的子树合并。

例如如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void split(int p,int x,int &l,int &r){
    if(!p)return (void)(l=r=0);
    down(p);
    if(val[p]<=x){
        l=p;
        split(son[p][1],x,son[p][1],r);
    }
    else{
        r=p;
        split(son[p][0],x,l,son[p][0]);
    }
    relax(p);
    up(p);
}
int getmin(int p){
    while(son[p][0])down(p),p=son[p][0];
    return val[p];
}
int getmax(int p){
    while(son[p][1])down(p),p=son[p][1];
    return val[p];
}
int Merge(int l,int r){
    if(!l||!r)return l+r;
    if(dat[l]>dat[r]){
        down(l);
        son[l][1]=Merge(son[l][1],r);
        up(l);
        relax(l);
        return l;
    }
    else{
        down(r);
        son[r][0]=Merge(l,son[r][0]);
        up(r);
        relax(r);
        return r;
    }
}
int merge(int l,int r){
    if(!l||!r)return l+r;
    down(l);down(r);
    if(getmax(l)<=getmin(r))return Merge(l,r);
    if(getmax(r)<=getmin(l))return Merge(r,l);
    if(dat[l]<dat[r])swap(l,r);
    int x,y;
    split(r,val[l],x,y);
    son[l][0]=merge(son[l][0],x);
    son[l][1]=merge(son[l][1],y);
    relax(l);
    up(l);
    return l;
}

若值域有 kk 段交，则上述 merge 复杂度显然为 O(klog⁡n)O(k\log n) 。

复杂度证明

结论：对于多棵平衡树的合并，复杂度不超过 O(nlog⁡nlog⁡V)O(n\log n\log V) 。

证明：

定义一颗平衡树 TT 的势能 ϕ(T)\phi(T) 为：若平衡树所维护的数从小到大为 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n ，则：

ϕ(T)=∑log⁡(ai−ai−1)\phi(T)=\sum \log(a_{i}-a_{i-1})

那么多棵平衡树的总初始势能为 O(nlog⁡V)O(n\log V) 。

接下来证明两棵树 T1,T2T_1,T_2 的合并会使势能减少 k−O(log⁡V)k-O(\log V) 。

设 T1+T2→TT_1+T_2\to T 。

那么势能的变化量为 ϕ(T1)+ϕ(T2)−ϕ(T)\phi(T_1)+\phi(T_2)-\phi(T) 。

极端情况下 T1,T2T_1,T_2 里面的每一段都只有一个数，那么不妨设这些数的距离分别为 d1,d2,⋯ ,dO(k)d_1,d_2,\cdots,d_{O(k)} 。

那么 ϕ(T1)+ϕ(T2)=∑log⁡(di+di+1)\phi(T_1)+\phi(T_2)=\displaystyle\sum \log(d_i+d_{i+1}) ， ϕ(T)=∑log⁡(di)\phi(T)=\displaystyle\sum \log(d_i) 。

那么：

ϕ(T1)+ϕ(T2)−ϕ(T)=∑log⁡(di+di+1)−∑log⁡(di)=(∑log⁡(di+di+1)−12log⁡(di)−12log⁡(di))−12log⁡(d1)−12log⁡(dm)=(∑log⁡(2(di+di+1)2)−log⁡(di)+log⁡(di+1)2)−O(log⁡V)=(∑log⁡(2)+log⁡((di+di+1)2)−log⁡(di)+log⁡(di+1)2)−O(log⁡V)=klog⁡(2)+(∑log⁡((di+di+1)2)−log⁡(di)+log⁡(di+1)2)−O(log⁡V)\begin{aligned} \phi(T_1)+\phi(T_2)-\phi(T) &= \displaystyle\sum \log(d_i+d_{i+1})-\displaystyle\sum \log(d_i) \\ &=(\displaystyle\sum \log(d_i+d_{i+1})-\frac{1}{2}\log(d_i)-\frac{1}{2}\log(d_i))-\frac{1}{2}\log(d_1)-\frac{1}{2}\log(d_m) \\ &=(\displaystyle\sum \log(\frac{2(d_i+d_{i+1})}{2})-\frac{\log(d_i)+\log(d_{i+1})}{2})-O(\log V)\\ &=(\displaystyle\sum \log(2)+\log(\frac{(d_i+d_{i+1})}{2})-\frac{\log(d_i)+\log(d_{i+1})}{2})-O(\log V)\\ &=k\log(2)+(\displaystyle\sum \log(\frac{(d_i+d_{i+1})}{2})-\frac{\log(d_i)+\log(d_{i+1})}{2})-O(\log V) \end{aligned}

首先，以上推导过程只依赖于 log⁡\log 而不依赖于其底数，所以我们不妨指定底数为 22 ，就有：

ϕ(T1)+ϕ(T2)−ϕ(T)=(∑log⁡((di+di+1)2)−log⁡(di)+log⁡(di+1)2)+k−O(log⁡V)\phi(T_1)+\phi(T_2)-\phi(T)=(\displaystyle\sum \log(\frac{(d_i+d_{i+1})}{2})-\frac{\log(d_i)+\log(d_{i+1})}{2})+k-O(\log V)

其次， log⁡\log 是一个上凸函数，那么 log⁡\log 就满足不等式（忽略条件）：

log⁡(a+b2)≥log⁡(a)+log⁡(b)2\log(\frac{a+b}{2})\ge\frac{\log(a)+\log(b)}{2}

代入到上式中可得：

log⁡((di+di+1)2)−log⁡(di)+log⁡(di+1)2≥0∑log⁡((di+di+1)2)−log⁡(di)+log⁡(di+1)2≥0ϕ(T1)+ϕ(T2)−ϕ(T)≥k−O(log⁡V)\log(\frac{(d_i+d_{i+1})}{2})-\frac{\log(d_i)+\log(d_{i+1})}{2}\ge 0 \\ \displaystyle\sum \log(\frac{(d_i+d_{i+1})}{2})-\frac{\log(d_i)+\log(d_{i+1})}{2}\ge 0\\ \phi(T_1)+\phi(T_2)-\phi(T)\ge k-O(\log V)

那么每次合并两棵平衡树的时间复杂度为 O(klog⁡n)O(k\log n) ，且势能减少 k−O(log⁡V)k-O(\log V) 。

那么就有：

∑kilog⁡V≤O(nlog⁡V)\sum k_i\log V\le O(n\log V)

∑ki≤O(nlog⁡V)\sum k_i \le O(n\log V)

∑kilog⁡n≤O(nlog⁡nlog⁡V)\sum k_i\log n \le O(n\log n\log V)

于是时间复杂度得到了证明，为 O(nlog⁡nlog⁡V)O(n\log n\log V) 。