🗂️Data StructureAdvanced

Implicit Treap

Key Points

  • •
    An implicit treap is a randomized balanced binary tree that treats array positions as keys without storing them explicitly.
  • •
    It supports expected O(log n) insertions and deletions at a position by splitting on subtree sizes and then merging.
  • •
    Range operations like reverse, cut, paste, and cyclic shift are implemented by 2–3 splits and 1–2 merges.
  • •
    The subtree size field lets you navigate by index: the inorder sequence is exactly the array order.
  • •
    Lazy propagation lets you reverse a whole range in O(1) by toggling a flag and swapping children on push.
  • •
    The expected height of an implicit treap is O(log n) because node priorities are random and form a random heap.
  • •
    This data structure is the backbone of rope-like editors for large strings and competitive programming sequence problems.
  • •
    Careful push and update functions are crucial to maintain size, sums, and lazy flags correctly.

Prerequisites

  • →Binary Search Trees (BSTs) — Understanding tree structure, inorder traversal, and how rotations or structural changes affect order is fundamental.
  • →Heap Property and Priority Queues — Treaps combine BST structure with heap ordering by priority; knowing heap invariants helps understand merge decisions.
  • →Order-Statistic Trees — Implicit treaps navigate by index using subtree sizes, mirroring order-statistic operations.
  • →Randomization and Expected Analysis — Expected O(log n) guarantees depend on random priorities; familiarity with expected-value reasoning is useful.
  • →Lazy Propagation — Range operations like reverse are applied lazily to maintain efficiency and correctness.
  • →Recursion and Call Stack — Split and merge are commonly implemented recursively; understanding stack behavior avoids mistakes.
  • →Asymptotic Complexity (Big-O) — To analyze the logarithmic expected time and linear space of operations.
  • →C++ Pointers and Dynamic Allocation — Treap nodes are heap-allocated and manipulated through raw pointers in typical contest implementations.

Detailed Explanation

Tap terms for definitions

01Overview

An implicit treap is a balanced binary search tree that does not store actual keys. Instead, it treats each node’s position in the inorder traversal as its key. This makes it perfect for representing dynamic arrays where you often need to insert, delete, or modify elements by index. The “treap” name comes from combining a binary search tree (BST) organized by key with a heap organized by a random priority. In an implicit treap, the BST order is simply the inorder position, so we only need to maintain subtree sizes to move by index. Random priorities keep the tree balanced in expectation, yielding O(log n) time per operation. Core operations are split and merge: split(T, k) cuts the first k elements into one treap and the rest into another; merge(A, B) joins two treaps where all elements of A come before those of B. By chaining a few splits and merges, we can implement index-based insert, delete, reverse, range sum, substring extraction, concatenation, and cyclic shifts. With lazy propagation, we can apply certain range updates (like reversing a segment) in O(1) per operation by delaying work until the next necessary traversal. In practice, implicit treaps are simple to code, fast, and memory efficient. They are heavily used in competitive programming for sequence problems, serve as a foundation for rope data structures in text editors, and avoid the pitfalls of linked lists or expensive array shifts.

02Intuition & Analogies

Imagine a long row of books on a shelf, where the position of a book matters more than its title. You want to insert a new book at position 5, remove the book at position 10, flip the order of books between positions 20 and 30, or rotate a chunk of books to the right. Doing this on a plain array means shifting many books, which is slow. On a linked list, you can insert cheaply but it takes a long time to walk to position 10 every time. An implicit treap stores the books in a binary tree where an inorder walk visits them left-to-right exactly in shelf order. Each node also stores how many books are in its left and right subtrees (its size). That means to find the k-th book, you look at the size of the left side: if the left has L books, then the current node is the (L+1)-th; go left if k <= L, go right if k > L+1. This precisely mimics indexing while still being a tree. To keep the tree well-shaped (not a broom or a chain), every node gets a random “priority ticket.” Think of it as drawing a random number when the book is added. The tree maintains that higher-priority books sit closer to the root, forming a “heap” by priority. Randomness prevents long chains from occurring too often, so the height stays around log n most of the time. Now the magic operations: split at k literally cuts the shelf into two parts after the k-th book by following tree pointers, and merge stitches two shelves back together while respecting the random-priority heap rule. To reverse a segment, you cut the shelf into three parts [0..l-1], [l..r], [r+1..], flip the middle by toggling a flag (so its children are swapped lazily), then paste everything back together. Cyclic shifts cut the segment into two pieces at the right boundary and re-glue in swapped order.

03Formal Definition

A treap is a binary tree where each node v has a key key(v) and a priority p(v). It maintains two invariants: (1) The inorder traversal follows the BST order on keys; (2) The node priorities satisfy the heap property (e.g., p(v) is smaller than the priorities of its children for a min-heap). If priorities are i.i.d. continuous random variables, the expected height is O(log n). In an implicit treap, we do not store key(v). Instead, the inorder rank (position) defines the key implicitly. Each node stores size(v) = 1 + size(left(v)) + size(right(v)). The position of the root is size(left(root)) + 1; more generally, navigation by index k proceeds as in an order-statistics tree using stored sizes. Define split(T, k) to return a pair (A, B) of treaps such that inorder(A) consists of the first k elements of inorder(T), and inorder(B) consists of the remaining elements. Define merge(A, B) to return a treap whose inorder is the concatenation inorder(A) ∘ inorder(B), assuming all elements of A precede all elements of B in the desired sequence. Implementations use recursion guided by priorities to satisfy the heap property while preserving inorder concatenation. For range operations, we allow lazy propagation flags. For example, a reverse flag rev(v) indicates that the inorder sequence of the subtree rooted at v is reversed. Pushing this flag swaps the children of v and toggles their rev flags, preserving aggregate fields (e.g., sums) that are invariant to reordering.

04When to Use

Use an implicit treap when you maintain a dynamic sequence and need fast index-based operations: insert/delete at arbitrary positions, split a sequence, concatenate sequences, reverse a substring, rotate a subarray, or compute aggregates over ranges (sum, min, max) with optional lazy updates. This is especially valuable when operations are intermixed online and the sequence can grow to hundreds of thousands of elements. Practical domains include competitive programming problems about permutations and sequences; implementing rope-like string editors that frequently cut/paste or reverse substrings; simulation logs where events are inserted by position; and maintaining playlists or task lists with frequent rearrangements. Compared to std::vector, implicit treaps avoid O(n) shifts for middle insertions/deletions. Compared to linked lists, they support O(log n) random access by index. Compared to segment trees, they support structural edits (insert/delete) naturally. Compared to balanced BSTs with explicit keys, they simplify indexing by using subtree sizes and avoid key updates after insertions. If you only need static range queries/updates without structural edits, a Fenwick or segment tree may be simpler and faster. If you need string operations with persistent snapshots or disk-backed storage, specialized ropes or B-trees may be better. But for in-memory, online, mixed sequence edits with range transforms, implicit treaps are a strong default.

⚠️Common Mistakes

• Forgetting to push lazy flags before descending or rotating during split/merge. Always call push(node) before using its children; otherwise, reversed segments or pending updates corrupt order and aggregates. • Not updating size/sum/min/max after modifying children. Always call pull(node) (or update) after changing left or right pointers to recompute size and aggregated fields. • Off-by-one errors in split by size. Decide on 0-based or 1-based indices and stick to it. A common convention: split(T, k) puts the first k elements (0..k-1) in the left treap. • Using poor randomness or non-unique priorities. Prefer a high-quality generator like std::mt19937 and allow 32–64-bit priorities. Equal priorities can degrade balancing if you impose a biased tiebreak. • Neglecting k normalization for rotations: use k' = ((k % len) + len) % len to handle negative k and k ≥ len. • Integer overflow in aggregates (like sum). Store sums as long long and be mindful of constraints. • Excess recursion depth if the RNG is degenerate. While expected height is O(log n), a worst-case height of O(n) is possible; ensure your platform’s recursion limit is safe or convert to iterative where necessary. • Memory leaks in contest code. While often ignored in short runs, consider destructors or pooled allocators for production or stress environments.

Key Formulas

Subtree Size

Explanation: The size of a node’s subtree equals one for the node itself plus the sizes of its left and right subtrees. This is the core quantity used to navigate by index.

Inorder Position

Explanation: The position of v equals how many nodes are to its left: nodes in its own left subtree plus nodes to the left of every ancestor where v lies in the ancestor’s right subtree. This formalizes index computation.

Expected Height

Explanation: For i.i.d. random priorities, the expected height of a treap on n nodes grows proportionally to log n. This underpins expected O(log n) operations.

Split Recurrence

Explanation: A split follows one branch (left or right) plus constant work at each step, so its cost is proportional to the tree height. The expected cost is logarithmic.

Merge Recurrence

Explanation: Similarly, merge descends a single path determined by priorities, doing constant work per node, leading to expected logarithmic time.

Lazy Reverse

Explanation: To apply a pending reverse on a node, swap its children and toggle their reverse flags, then clear the current flag. Aggregates like sum remain correct because reversal only reorders.

Subtree Sum

Explanation: Maintains the sum of values in each subtree, enabling O(1) query after isolating a range with splits. Use 64-bit types to avoid overflow.

Normalized Rotation

Explanation: When rotating a segment of length L by k, normalize k into [0, L) to handle negative and large rotations. A rotation by 0 is a no-op.

Rotate by Splits/Merges

Explanation: Split into A=[0..l-1], C=[l..r], B=[r+1..], then split C at L-k into and , and merge as A + + + B. Each split/merge is O(log n) expected.

Build Complexity

Explanation: Inserting n items one-by-one costs O(n log n) expected, while constructing a Cartesian tree from indices with given priorities builds the treap in linear time.

Complexity Analysis

Let n be the number of elements in the sequence. With independent random priorities, the treap’s expected height is O(log n). Operations are composed of a constant number of split and merge calls. Each split or merge descends one path, performing O(1) work per level (push a flag, compare priorities, rotate pointers, pull aggregates). Therefore the expected time for insert-at-position, erase-at-position, kth-element access, range reverse, range sum, and cyclic shift is O(log n) each. Worst-case time can reach O(n) if priorities are adversarial (e.g., equal or poorly randomized), but using a robust RNG (std::mt19937) and wide priorities keeps this risk negligible in practice. Lazy propagation does not change the asymptotic cost: toggling a reverse flag is O(1), and pushing happens only along accessed paths, preserving O(log n) per operation in expectation. Space usage is O(n) for nodes, each storing value, priority, two child pointers, metadata (size, aggregates), and a few booleans. There is additional O(h) space on the call stack per operation (h is tree height), which is O(log n) expected. Building by sequential inserts costs O(n log n) expected time; an O(n) build is possible via a Cartesian tree over priorities if all items are known upfront. Aggregations like sums or mins add only O(1) space per node and retain the same time bounds.

Code Examples

Core implicit treap: insert, erase, and access by position
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int val;                 // value stored at this position
6    uint32_t pr;             // random priority
7    int sz;                  // subtree size
8    Node *l, *r;
9    Node(int v, uint32_t p) : val(v), pr(p), sz(1), l(nullptr), r(nullptr) {}
10};
11
12static mt19937 rng((uint32_t)chrono::high_resolution_clock::now().time_since_epoch().count());
13
14int getsz(Node* t) { return t ? t->sz : 0; }
15
16void pull(Node* t) {
17    if (!t) return;
18    t->sz = 1 + getsz(t->l) + getsz(t->r);
19}
20
21// Split by size: put first k elements into a, the rest into b
22void split(Node* t, Node*& a, Node*& b, int k) {
23    if (!t) { a = b = nullptr; return; }
24    int leftsz = getsz(t->l);
25    if (k <= leftsz) {
26        // Entire split is in the left subtree
27        split(t->l, a, t->l, k);
28        b = t;
29        pull(b);
30    } else {
31        // Take current node and some from the right subtree
32        split(t->r, t->r, b, k - leftsz - 1);
33        a = t;
34        pull(a);
35    }
36}
37
38Node* merge(Node* a, Node* b) {
39    if (!a) return b;
40    if (!b) return a;
41    if (a->pr < b->pr) {
42        a->r = merge(a->r, b);
43        pull(a);
44        return a;
45    } else {
46        b->l = merge(a, b->l);
47        pull(b);
48        return b;
49    }
50}
51
52void insertAt(Node*& root, int pos, int val) {
53    Node *a, *b;
54    split(root, a, b, pos);                    // [0..pos-1], [pos..]
55    Node* m = new Node(val, rng());
56    root = merge(merge(a, m), b);
57}
58
59void eraseAt(Node*& root, int pos) {
60    Node *a, *b, *c;
61    split(root, a, b, pos);                    // a=[0..pos-1], b=[pos..]
62    split(b, b, c, 1);                         // b=[pos], c=[pos+1..]
63    // delete b; // In contest code we may skip explicit deletion
64    root = merge(a, c);
65}
66
67// Access the k-th (0-based) element's value
68int kth(Node* root, int k) {
69    Node* t = root;
70    while (t) {
71        int leftsz = getsz(t->l);
72        if (k < leftsz) t = t->l;
73        else if (k == leftsz) return t->val;
74        else { k -= leftsz + 1; t = t->r; }
75    }
76    throw runtime_error("Index out of bounds");
77}
78
79void inorder(Node* t, vector<int>& out) {
80    if (!t) return;
81    inorder(t->l, out);
82    out.push_back(t->val);
83    inorder(t->r, out);
84}
85
86int main() {
87    ios::sync_with_stdio(false);
88    cin.tie(nullptr);
89
90    Node* root = nullptr;
91    vector<int> init = {10, 20, 30};
92    for (int i = 0; i < (int)init.size(); ++i) insertAt(root, i, init[i]);
93
94    vector<int> v;
95    inorder(root, v);
96    cout << "Initial: ";
97    for (int x : v) cout << x << ' ';
98    cout << '\n';
99
100    insertAt(root, 1, 99); // [10, 99, 20, 30]
101    v.clear(); inorder(root, v);
102    cout << "After insert at pos 1: ";
103    for (int x : v) cout << x << ' ';
104    cout << '\n';
105
106    eraseAt(root, 2); // remove element at index 2 -> [10, 99, 30]
107    v.clear(); inorder(root, v);
108    cout << "After erase at pos 2: ";
109    for (int x : v) cout << x << ' ';
110    cout << '\n';
111
112    cout << "kth(root, 1) = " << kth(root, 1) << '\n';
113    return 0;
114}
115

This program implements the essential implicit treap with split by size and merge. It supports insertion and deletion at arbitrary positions and retrieving the k-th element. The inorder traversal yields the current sequence. Random priorities keep the tree balanced in expectation.

Time: Each insertAt, eraseAt, and kth is O(log n) expected.Space: O(n) for nodes; O(log n) expected recursion stack for split/merge.
Range reverse with lazy propagation and range sum query
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int val;
6    uint32_t pr;
7    int sz;
8    long long sum;          // subtree sum
9    bool rev;               // lazy reverse flag
10    Node *l, *r;
11    Node(int v, uint32_t p) : val(v), pr(p), sz(1), sum(v), rev(false), l(nullptr), r(nullptr) {}
12};
13
14static mt19937 rng((uint32_t)chrono::high_resolution_clock::now().time_since_epoch().count());
15
16int getsz(Node* t) { return t ? t->sz : 0; }
17long long getsum(Node* t) { return t ? t->sum : 0LL; }
18
19void push(Node* t) {
20    if (!t || !t->rev) return;
21    // Apply reverse lazily: swap children and toggle children's flags
22    swap(t->l, t->r);
23    if (t->l) t->l->rev = !t->l->rev;
24    if (t->r) t->r->rev = !t->r->rev;
25    t->rev = false;
26}
27
28void pull(Node* t) {
29    if (!t) return;
30    t->sz = 1 + getsz(t->l) + getsz(t->r);
31    t->sum = (long long)t->val + getsum(t->l) + getsum(t->r);
32}
33
34void split(Node* t, Node*& a, Node*& b, int k) {
35    if (!t) { a = b = nullptr; return; }
36    push(t);
37    int leftsz = getsz(t->l);
38    if (k <= leftsz) {
39        split(t->l, a, t->l, k);
40        b = t;
41        pull(b);
42    } else {
43        split(t->r, t->r, b, k - leftsz - 1);
44        a = t;
45        pull(a);
46    }
47}
48
49Node* merge(Node* a, Node* b) {
50    if (!a) return b;
51    if (!b) return a;
52    if (a->pr < b->pr) {
53        push(a);
54        a->r = merge(a->r, b);
55        pull(a);
56        return a;
57    } else {
58        push(b);
59        b->l = merge(a, b->l);
60        pull(b);
61        return b;
62    }
63}
64
65void insertAt(Node*& root, int pos, int val) {
66    Node *a, *b;
67    split(root, a, b, pos);
68    Node* m = new Node(val, rng());
69    root = merge(merge(a, m), b);
70}
71
72void rangeReverse(Node*& root, int l, int r) { // reverse inclusive range [l, r]
73    if (l > r) return;
74    Node *A, *BC, *B, *C;
75    split(root, A, BC, l);                 // A=[0..l-1], BC=[l..]
76    split(BC, B, C, r - l + 1);            // B=[l..r], C=[r+1..]
77    if (B) B->rev = !B->rev;               // toggle reverse lazily
78    root = merge(merge(A, B), C);
79}
80
81long long rangeSum(Node*& root, int l, int r) {
82    Node *A, *BC, *B, *C;
83    split(root, A, BC, l);
84    split(BC, B, C, r - l + 1);
85    long long ans = getsum(B);
86    root = merge(merge(A, B), C);          // restore
87    return ans;
88}
89
90void inorder(Node* t, vector<int>& out) {
91    if (!t) return;
92    push(t);
93    inorder(t->l, out);
94    out.push_back(t->val);
95    inorder(t->r, out);
96}
97
98int main() {
99    ios::sync_with_stdio(false);
100    cin.tie(nullptr);
101
102    Node* root = nullptr;
103    // Build [1..10]
104    for (int i = 0; i < 10; ++i) insertAt(root, i, i + 1);
105
106    vector<int> v;
107    inorder(root, v);
108    cout << "Initial: ";
109    for (int x : v) cout << x << ' ';
110    cout << '\n';
111
112    rangeReverse(root, 2, 7); // reverse positions 2..7 (0-based)
113    v.clear(); inorder(root, v);
114    cout << "After reverse [2..7]: ";
115    for (int x : v) cout << x << ' ';
116    cout << '\n';
117
118    long long s = rangeSum(root, 3, 8);
119    cout << "Sum [3..8] = " << s << '\n';
120    return 0;
121}
122

This version adds a reverse lazy flag and a subtree sum. rangeReverse isolates [l..r] via two splits, toggles the reverse flag on the middle treap, and merges back. rangeSum isolates and reads the precomputed sum. push and pull ensure correctness of order and aggregates.

Time: O(log n) expected per rangeReverse and rangeSum.Space: O(n) nodes plus O(log n) expected recursion stack.
Cyclic right shift (rotate) of a subarray using split and merge
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    int val; uint32_t pr; int sz; bool rev; Node *l, *r;
6    Node(int v, uint32_t p): val(v), pr(p), sz(1), rev(false), l(nullptr), r(nullptr) {}
7};
8
9static mt19937 rng((uint32_t)chrono::high_resolution_clock::now().time_since_epoch().count());
10
11int getsz(Node* t){ return t? t->sz : 0; }
12void push(Node* t){ if(!t || !t->rev) return; swap(t->l,t->r); if(t->l) t->l->rev^=1; if(t->r) t->r->rev^=1; t->rev=false; }
13void pull(Node* t){ if(!t) return; t->sz = 1 + getsz(t->l) + getsz(t->r); }
14
15void split(Node* t, Node*& a, Node*& b, int k){
16    if(!t){ a=b=nullptr; return; }
17    push(t);
18    int L = getsz(t->l);
19    if(k <= L){ split(t->l, a, t->l, k); b=t; pull(b); }
20    else { split(t->r, t->r, b, k-L-1); a=t; pull(a); }
21}
22
23Node* merge(Node* a, Node* b){
24    if(!a) return b; if(!b) return a;
25    if(a->pr < b->pr){ push(a); a->r = merge(a->r,b); pull(a); return a; }
26    else { push(b); b->l = merge(a,b->l); pull(b); return b; }
27}
28
29void insertAt(Node*& root,int pos,int val){ Node *A,*B; split(root,A,B,pos); root = merge(merge(A,new Node(val,rng())),B); }
30
31void rotateRight(Node*& root, int l, int r, int k){
32    if(l>r) return; Node *A,*BC,*B,*C; split(root,A,BC,l); split(BC,B,C,r-l+1);
33    int len = getsz(B); if(len<=1){ root = merge(merge(A,B),C); return; }
34    k = ((k % len) + len) % len; if(k==0){ root = merge(merge(A,B),C); return; }
35    Node *H,*T; // split B into head and tail: head has len-k elements
36    split(B,H,T,len-k); // B = [H | T], rotate right by k => [T | H]
37    B = merge(T,H);
38    root = merge(merge(A,B),C);
39}
40
41void inorder(Node* t, vector<int>& out){ if(!t) return; push(t); inorder(t->l,out); out.push_back(t->val); inorder(t->r,out); }
42
43int main(){
44    ios::sync_with_stdio(false); cin.tie(nullptr);
45    Node* root = nullptr;
46    for(int i=0;i<8;++i) insertAt(root,i,i+1); // [1..8]
47    vector<int> v; inorder(root,v);
48    cout << "Initial: "; for(int x:v) cout<<x<<' '; cout<<'\n'; v.clear();
49
50    rotateRight(root,2,6,2); // rotate [2..6] by 2 to the right
51    inorder(root,v);
52    cout << "After rotateRight [2..6] by 2: "; for(int x:v) cout<<x<<' '; cout<<'\n';
53    return 0;
54}
55

The rotateRight function performs a cyclic shift on a subarray [l..r] by k positions to the right. It splits the treap into three parts, splits the middle part into head and tail at len - k, merges in swapped order, then reattaches the outer parts. Lazy reverse support is included but unused here.

Time: O(log n) expected for a rotation (constant number of splits/merges).Space: O(n) nodes, O(log n) expected recursion stack.
Rope-style cut, concatenate, and substring on strings using an implicit treap
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Node {
5    char ch; uint32_t pr; int sz; Node *l, *r;
6    Node(char c, uint32_t p): ch(c), pr(p), sz(1), l(nullptr), r(nullptr) {}
7};
8
9static mt19937 rng((uint32_t)chrono::high_resolution_clock::now().time_since_epoch().count());
10
11int getsz(Node* t){ return t? t->sz:0; }
12void pull(Node* t){ if(!t) return; t->sz = 1 + getsz(t->l) + getsz(t->r); }
13
14void split(Node* t, Node*& a, Node*& b, int k){
15    if(!t){ a=b=nullptr; return; }
16    int L = getsz(t->l);
17    if(k <= L){ split(t->l, a, t->l, k); b=t; pull(b); }
18    else { split(t->r, t->r, b, k-L-1); a=t; pull(a); }
19}
20
21Node* merge(Node* a, Node* b){
22    if(!a) return b; if(!b) return a;
23    if(a->pr < b->pr){ a->r = merge(a->r,b); pull(a); return a; }
24    else { b->l = merge(a,b->l); pull(b); return b; }
25}
26
27Node* buildFromString(const string& s){
28    Node* root = nullptr;
29    for (int i=0;i<(int)s.size();++i){
30        Node *A,*B; split(root,A,B,i);
31        root = merge(merge(A,new Node(s[i],rng())),B);
32    }
33    return root;
34}
35
36string toString(Node* t){
37    string out; out.reserve(getsz(t));
38    // iterative inorder to avoid recursion limits (simple stack)
39    vector<Node*> st; Node* cur = t; 
40    while(cur || !st.empty()){
41        while(cur){ st.push_back(cur); cur = cur->l; }
42        cur = st.back(); st.pop_back();
43        out.push_back(cur->ch);
44        cur = cur->r;
45    }
46    return out;
47}
48
49// Cut substring [l..r] and return it as a separate treap; original loses that substring
50Node* cut(Node*& root, int l, int r){
51    Node *A,*BC,*B,*C; split(root,A,BC,l); split(BC,B,C,r-l+1); root = merge(A,C); return B;
52}
53
54// Paste treap mid at position pos into root
55void paste(Node*& root, Node* mid, int pos){ Node *A,*B; split(root,A,B,pos); root = merge(merge(A,mid),B); }
56
57int main(){
58    ios::sync_with_stdio(false); cin.tie(nullptr);
59    Node* A = buildFromString("hello ");
60    Node* B = buildFromString("world!");
61
62    Node* AB = merge(A,B); // concatenate
63    cout << toString(AB) << '\n';
64
65    // Move substring [0..4] ("hello") to the end
66    Node* mid = cut(AB, 0, 4);
67    paste(AB, mid, getsz(AB));
68    cout << toString(AB) << '\n';
69
70    // Extract substring [0..4] as a new string (" world")
71    Node* sub = cut(AB, 0, 5);
72    cout << toString(sub) << '\n';
73    cout << toString(AB) << '\n';
74    return 0;
75}
76

This example shows rope-like operations for strings: build, concatenate (merge), cut a substring (two splits and a merge), and paste at a position (two merges). The inorder traversal reconstructs the current text.

Time: Each cut or paste is O(log n) expected; building by sequential insert is O(n log n) expected.Space: O(n) nodes; O(log n) expected recursion stack during split/merge.