FHQ Treap(无旋)简介

admin

https://blog.csdn.net/pengwill97 ... gCommendFromBaidu-1

admin

1. void split(int rt, int & a, int & b, int val) {
   
2.     if (rt == 0) {
   
3.         a = b = 0;
   
4.         return;
   
5.     }
   
6.     if (tree[rt].val <= val) {
   
7.         a = rt;
   
8.         split(tree[rt].rc, tree[a].rc, b, val);
   
9.     } else {
   
10.         b = rt;
    
11.         split(tree[rt].lc, a, tree[b].lc, val);
    
12.     }
    
13.     update(rt);
    
14. }

复制代码

admin

1. void merge(int & rt, int a, int b) {
   
2.     // 前提：a的权值全部 < b的权值
   
3.     if (a == 0 || b == 0) {
   
4.         rt = a + b;
   
5.         return;
   
6.     }
   
7.     if (tree[a].rnk < tree[b].rnk) {
   
8.         rt = a;
   
9.         merge(tree[rt].rc, tree[a].rc, b);
   
10.     } else {
    
11.         rt = b;
    
12.         merge(tree[rt].lc, a, tree[b].lc);
    
13.     }
    
14.     update(rt);
    
15. }

复制代码