Treap

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Rotation-based treap that supports duplicates (multiset),
5
// rank (count of keys < x), kth smallest, lower_bound, insert, erase.
6
// Expected O(log n) per operation.
7
8
struct Node {
9
    int key;               // BST key
10
    uint32_t pri;          // heap priority (max-heap)
11
    int cnt;               // multiplicity of this key
12
    int sz;                // size = cnt + size(left) + size(right)
13
    Node *l, *r;
14
    Node(int k, uint32_t p): key(k), pri(p), cnt(1), sz(1), l(nullptr), r(nullptr) {}
15
};
16
17
static mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
18
19
int getsz(Node* t){ return t ? t->sz : 0; }
20
void pull(Node* t){ if(t) t->sz = t->cnt + getsz(t->l) + getsz(t->r); }
21
22
void rotateRight(Node* &t){
23
    Node* x = t->l;              // x becomes new root of this subtree
24
    t->l = x->r;                 // move x's right subtree to t's left
25
    x->r = t;                    // t becomes right child of x
26
    pull(t); pull(x);            // update sizes bottom-up
27
    t = x;                       // set new root
28
}
29
30
void rotateLeft(Node* &t){
31
    Node* x = t->r;              // x becomes new root of this subtree
32
    t->r = x->l;                 // move x's left subtree to t's right
33
    x->l = t;                    // t becomes left child of x
34
    pull(t); pull(x);            // update sizes bottom-up
35
    t = x;                       // set new root
36
}
37
38
void insert(Node* &t, int key){
39
    if(!t){ t = new Node(key, rng()); return; }
40
    if(key == t->key){
41
        t->cnt++; pull(t); return;
42
    } else if(key < t->key){
43
        insert(t->l, key);
44
        if(t->l && t->l->pri > t->pri) rotateRight(t);
45
    } else {
46
        insert(t->r, key);
47
        if(t->r && t->r->pri > t->pri) rotateLeft(t);
48
    }
49
    pull(t);
50
}
51
52
void erase(Node* &t, int key){
53
    if(!t) return;
54
    if(key == t->key){
55
        if(t->cnt > 1){ t->cnt--; pull(t); return; }
56
        // remove node: rotate a higher-priority child up until node has <=1 child
57
        if(!t->l){ Node* tmp = t; t = t->r; delete tmp; return; }
58
        if(!t->r){ Node* tmp = t; t = t->l; delete tmp; return; }
59
        if(t->l->pri > t->r->pri){ rotateRight(t); erase(t->r, key); }
60
        else { rotateLeft(t); erase(t->l, key); }
61
    } else if(key < t->key){
62
        erase(t->l, key);
63
    } else {
64
        erase(t->r, key);
65
    }
66
    pull(t);
67
}
68
69
// count of keys strictly less than x
70
int rankOf(Node* t, int x){
71
    if(!t) return 0;
72
    if(x <= t->key) return rankOf(t->l, x);
73
    return getsz(t->l) + t->cnt + rankOf(t->r, x);
74
}
75
76
// kth smallest (1-indexed); assumes 1 <= k <= size
77
int kth(Node* t, int k){
78
    if(!t) throw runtime_error("k out of bounds");
79
    int left = getsz(t->l);
80
    if(k <= left) return kth(t->l, k);
81
    if(k <= left + t->cnt) return t->key;
82
    return kth(t->r, k - left - t->cnt);
83
}
84
85
// lower_bound: smallest key >= x; returns pair(found?, value)
86
pair<bool,int> lower_bound(Node* t, int x){
87
    int ans = 0; bool ok = false;
88
    while(t){
89
        if(t->key >= x){ ans = t->key; ok = true; t = t->l; }
90
        else t = t->r;
91
    }
92
    return {ok, ans};
93
}
94
95
// Simple demo
96
int main(){
97
    ios::sync_with_stdio(false);
98
    cin.tie(nullptr);
99
100
    Node* root = nullptr;
101
    vector<int> a = {5, 1, 7, 3, 5, 9, 2, 5};
102
    for(int x : a) insert(root, x);
103
104
    cout << "size = " << getsz(root) << "\n";                // 8
105
    cout << "rankOf(5) = " << rankOf(root, 5) << "\n";        // count of keys < 5
106
    cout << "kth(4) = " << kth(root, 4) << "\n";              // 4th smallest key
107
108
    auto lb = lower_bound(root, 6);
109
    cout << "lower_bound(6): ";
110
    if(lb.first) cout << lb.second << "\n"; else cout << "none\n";
111
112
    erase(root, 5);  // removes one occurrence of 5
113
    cout << "size after erasing one 5 = " << getsz(root) << "\n";
114
115
    // Clean-up omitted for brevity (would require a post-order delete)
116
    return 0;
117
}
118

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// FHQ treap: operations implemented via split/merge only (no explicit rotations).
5
// Demonstrates insert, erase by key, and delete-by-range [L, R] using two splits.
6
7
struct Node {
8
    int key;                 // BST key (assumed unique in this demo)
9
    uint32_t pri;            // heap priority (max-heap)
10
    int sz;                  // subtree size
11
    Node *l, *r;
12
    Node(int k, uint32_t p): key(k), pri(p), sz(1), l(nullptr), r(nullptr) {}
13
};
14
15
static mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
16
17
int getsz(Node* t){ return t ? t->sz : 0; }
18
void pull(Node* t){ if(t) t->sz = 1 + getsz(t->l) + getsz(t->r); }
19
20
// Split by key: L has keys < x, R has keys >= x
21
void split(Node* t, int x, Node* &L, Node* &R){
22
    if(!t){ L = R = nullptr; return; }
23
    if(t->key < x){
24
        split(t->r, x, t->r, R);
25
        L = t; pull(L);
26
    } else {
27
        split(t->l, x, L, t->l);
28
        R = t; pull(R);
29
    }
30
}
31
32
// Merge assumes all keys in L < all keys in R
33
Node* merge(Node* L, Node* R){
34
    if(!L || !R) return L ? L : R;
35
    if(L->pri > R->pri){
36
        L->r = merge(L->r, R);
37
        pull(L); return L;
38
    } else {
39
        R->l = merge(L, R->l);
40
        pull(R); return R;
41
    }
42
}
43
44
Node* insert(Node* root, int key){
45
    Node *A, *B; split(root, key, A, B);
46
    Node* m = new Node(key, rng());
47
    return merge(merge(A, m), B);
48
}
49
50
Node* eraseKey(Node* root, int key){
51
    Node *A, *B, *C;             // A: < key, B: [key, +inf)
52
    split(root, key, A, B);
53
    split(B, key+1, B, C);       // B: == key, C: > key
54
    // delete all nodes in B (here keys are unique, so B is at most one node)
55
    // In general, iterate and delete B subtree
56
    // Freeing memory:
57
    function<void(Node*)> del = [&](Node* t){ if(!t) return; del(t->l); del(t->r); delete t; };
58
    del(B);
59
    return merge(A, C);
60
}
61
62
// Delete all keys in [L, R]
63
Node* eraseRange(Node* root, int Lb, int Rb){
64
    Node *A, *B, *C; // A: < Lb, B: [Lb, +inf)
65
    split(root, Lb, A, B);
66
    Node *M, *C2;    // M: [Lb, Rb], C2: > Rb
67
    split(B, Rb+1, M, C2);
68
    function<void(Node*)> del = [&](Node* t){ if(!t) return; del(t->l); del(t->r); delete t; };
69
    del(M);
70
    return merge(A, C2);
71
}
72
73
int main(){
74
    ios::sync_with_stdio(false);
75
    cin.tie(nullptr);
76
77
    Node* root = nullptr;
78
    vector<int> keys = {10, 5, 20, 7, 15, 30, 3, 8};
79
    for(int k : keys) root = insert(root, k);
80
81
    cout << "size = " << getsz(root) << "\n";  // 8
82
    root = eraseKey(root, 7);
83
    cout << "size after erase 7 = " << getsz(root) << "\n";  // 7
84
85
    root = eraseRange(root, 8, 18); // remove keys in [8,18]: 8,10,15
86
    cout << "size after erase [8,18] = " << getsz(root) << "\n"; // 4
87
88
    // Clean-up omitted for brevity
89
    return 0;
90
}
91

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Implicit treap: indices are implicit via in-order positions.
5
// Supports: insert at position, erase range, reverse range, and range sum.
6
7
struct Node {
8
    long long val;       // value stored at this position
9
    uint32_t pri;        // random priority (max-heap)
10
    int sz;              // subtree size (number of elements)
11
    long long sum;       // subtree sum aggregate
12
    bool rev;            // lazy reverse flag
13
    Node *l, *r;
14
    Node(long long v, uint32_t p): val(v), pri(p), sz(1), sum(v), rev(false), l(nullptr), r(nullptr) {}
15
};
16
17
static mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
18
19
int getsz(Node* t){ return t ? t->sz : 0; }
20
long long getsum(Node* t){ return t ? t->sum : 0LL; }
21
22
void push(Node* t){
23
    if(t && t->rev){
24
        t->rev = false;
25
        swap(t->l, t->r);
26
        if(t->l) t->l->rev ^= 1;
27
        if(t->r) t->r->rev ^= 1;
28
    }
29
}
30
31
void pull(Node* t){
32
    if(!t) return;
33
    t->sz = 1 + getsz(t->l) + getsz(t->r);
34
    t->sum = t->val + getsum(t->l) + getsum(t->r);
35
}
36
37
// Split by index k: first k elements go to A, rest to B (0-based k)
38
void split(Node* t, int k, Node* &A, Node* &B){
39
    if(!t){ A = B = nullptr; return; }
40
    push(t);
41
    int left = getsz(t->l);
42
    if(k <= left){
43
        split(t->l, k, A, t->l);
44
        B = t; pull(B);
45
    } else {
46
        split(t->r, k - left - 1, t->r, B);
47
        A = t; pull(A);
48
    }
49
}
50
51
Node* merge(Node* A, Node* B){
52
    if(!A || !B) return A ? A : B;
53
    if(A->pri > B->pri){
54
        push(A);
55
        A->r = merge(A->r, B);
56
        pull(A); return A;
57
    } else {
58
        push(B);
59
        B->l = merge(A, B->l);
60
        pull(B); return B;
61
    }
62
}
63
64
// Insert value v at position pos (0-based)
65
Node* insertAt(Node* root, int pos, long long v){
66
    Node *A, *B; split(root, pos, A, B);
67
    Node* m = new Node(v, rng());
68
    return merge(merge(A, m), B);
69
}
70
71
// Erase range [l, r] inclusive (0-based)
72
Node* eraseRange(Node* root, int l, int r){
73
    Node *A, *B, *C;            // A: [0, l-1], B: [l, n-1]
74
    split(root, l, A, B);
75
    Node *M, *C2;               // M: [l, r], C2: [r+1, n-1]
76
    split(B, r - l + 1, M, C2);
77
    function<void(Node*)> del = [&](Node* t){ if(!t) return; del(t->l); del(t->r); delete t; };
78
    del(M);
79
    return merge(A, C2);
80
}
81
82
// Reverse range [l, r]
83
Node* reverseRange(Node* root, int l, int r){
84
    Node *A, *B, *C; split(root, l, A, B);
85
    Node *M, *C2; split(B, r - l + 1, M, C2);
86
    if(M) M->rev ^= 1;          // toggle reverse flag
87
    return merge(A, merge(M, C2));
88
}
89
90
// Range sum query on [l, r]
91
long long rangeSum(Node* &root, int l, int r){
92
    Node *A, *B, *C; split(root, l, A, B);
93
    Node *M, *C2; split(B, r - l + 1, M, C2);
94
    long long ans = getsum(M);
95
    root = merge(A, merge(M, C2)); // restore
96
    return ans;
97
}
98
99
int main(){
100
    ios::sync_with_stdio(false);
101
    cin.tie(nullptr);
102
103
    Node* root = nullptr;
104
    // Build array [1, 2, 3, 4, 5]
105
    for(int i = 0; i < 5; ++i) root = insertAt(root, i, i+1);
106
107
    cout << "sum[0,4] = " << rangeSum(root, 0, 4) << "\n"; // 15
108
    root = reverseRange(root, 1, 3);                        // array becomes [1,4,3,2,5]
109
    cout << "sum[1,3] = " << rangeSum(root, 1, 3) << "\n"; // 4+3+2 = 9
110
111
    root = eraseRange(root, 2, 3);                          // erase positions 2..3 -> [1,4,5]
112
    cout << "sum[0,2] = " << rangeSum(root, 0, 2) << "\n"; // 10
113
114
    // Clean-up omitted for brevity
115
    return 0;
116
}
117