Implicit Treaps

An implicit treap is a randomized balanced binary tree representing a sequence. Its in-order traversal is the sequence order; a node's position is implicit in subtree sizes, rather than stored as a fixed key. This permits inserting or deleting at an index and reversing an interval without shifting a whole vector. Random priorities maintain expected logarithmic height, while split and merge express all sequence operations. This lesson implements insertion, deletion, range reversal, and range sum. It uses lazy reversal and long long sums; indices exposed to users are 1-based.

Prerequisites: Binary trees, recursion, subtree size/sum, randomized balancing, lazy propagation.

Build the idea

1. Two invariants at once

   In-order traversal gives the sequence. Priorities satisfy a max-heap condition: each parent has priority at least that of its children. Store size and sum for every subtree. Once child pointers change, pull recomputes size=1+leftSize+rightSize and sum=value+leftSum+rightSum. Random independent priorities make the expected shape behave like a random BST; they do not provide deterministic worst-case logarithmic height.

2. Split by a count

   split(t,k) returns the first k elements as one tree and the rest as another. If the left subtree has at least k elements, split inside it and reconnect the returned right piece as t's left child. Otherwise t belongs to the first piece; split the right child after skipping leftSize+1 elements. Pull t before returning. A count is used internally: split(t,0) produces an empty first piece.

3. Merge adjacent sequences

   merge(a,b) requires every sequence element of a to precede every element of b. Choose the root with larger priority, recursively merge at its touching boundary, and pull. There is no comparison of stored values: an implicit treap maintains positions, not sorted key order. Inserting at position p splits after p-1 elements, then merges left, new node, right.

4. Lazy interval reversal

   Isolate [l,r] with two splits: first after l-1 elements, then after r-l+1. Reversal swaps a node's children and toggles a flag indicating that each child's sequence also needs reversing. push sends this flag to children before any split or merge descends. Sum and size do not change under reversal, but left/right order does. Omitting push can split the wrong logical position even when totals look correct.

5. Worked sequence and limits

   Starting [1,2,3,4], reverse [2,4] to get [1,4,3,2]. Insert 9 at position 3 to get [1,4,9,3,2]. Delete position 2 to get [1,9,3,2], whose total is 15. A sum query temporarily isolates an interval, reads its aggregate, then merges all pieces back. The implementation uses an index pool, avoiding dangling pointers during vector growth. Deleted nodes stay allocated; memory therefore depends on all insertions, not only current length. Recursion depth is expected logarithmic, but can become linear in an unlucky or adversarial shape.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<random>
#include<chrono>
#include<utility>
#include<algorithm>
using namespace std;
struct Node{
    long long value=0,sum=0;
    unsigned long long priority=0;
    int left=0,right=0,size=0;
    bool rev=false;
};
struct Treap{
    vector<Node>t=vector<Node>(1); // Null node has size and sum zero.
    mt19937_64 rng{(unsigned long long)chrono::steady_clock::now().time_since_epoch().count()};
    int make(long long x){
        Node a;
        a.value=a.sum=x;
        a.priority=rng();
        a.size=1;
        t.push_back(a);
        return (int)t.size()-1;
    }
    int size(int p)const{
        return t[p].size;
    }
    // Recompute aggregates whenever child links change.
    void pull(int p){
        t[p].size=1+size(t[p].left)+size(t[p].right);
        t[p].sum=t[p].value+t[t[p].left].sum+t[t[p].right].sum;
    }
    // Reversal changes order, but preserves size and sum.
    void reverseNode(int p){
        if(p){
            swap(t[p].left,t[p].right);
            t[p].rev=!t[p].rev;
        }
    }
    // Make pending reversals visible before descending by implicit position.
    void push(int p){
        if(p&&t[p].rev){
            reverseNode(t[p].left);
            reverseNode(t[p].right);
            t[p].rev=false;
        }
    }
    pair<int,int>split(int p,int k){ // First k elements, then the remainder.
        if(!p){
            return {0,0};
        }
        push(p);
        if(size(t[p].left)>=k){
            auto parts=split(t[p].left,k);
            t[p].left=parts.second;
            pull(p);
            return {parts.first,p};
        }
        auto parts=split(t[p].right,k-size(t[p].left)-1);
        t[p].right=parts.first;
        pull(p);
        return {p,parts.second};
    }
    // All sequence elements of a must precede those of b; compare priorities.
    int merge(int a,int b){
        if(!a||!b){
            return a?a:b;
        }
        push(a);
        push(b);
        if(t[a].priority>=t[b].priority){
            int child=merge(t[a].right,b);
            t[a].right=child;
            pull(a);
            return a;
        }
        int child=merge(a,t[b].left);
        t[b].left=child;
        pull(b);
        return b;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    Treap tr;
    int root=0;
    for(int i=0;i<n;i++){
        long long x;
        cin>>x;
        int node=tr.make(x);
        root=tr.merge(root,node);
    }
    while(q--){
        char op;
        cin>>op;
        if(op=='I'){
            int p;
            long long x;
            cin>>p>>x;
            auto ab=tr.split(root,p-1);
            int node=tr.make(x);
            root=tr.merge(tr.merge(ab.first,node),ab.second);
        }
        else if(op=='D'){
            int p;
            cin>>p;
            auto ab=tr.split(root,p-1);
            auto bc=tr.split(ab.second,1);
            root=tr.merge(ab.first,bc.second);
        }
        else{
            int l,r;
            cin>>l>>r;
            // Isolate [l,r], operate on it, then restore every sequence piece.
            auto ab=tr.split(root,l-1);
            auto bc=tr.split(ab.second,r-l+1);
            if(op=='R'){
                tr.reverseNode(bc.first);
            }
            else{
                cout<<tr.t[bc.first].sum<<'\n';
            }
            root=tr.merge(ab.first,tr.merge(bc.first,bc.second));
        }
    }
}

Complexity analysis

Each split/merge takes expected O(log n), worst-case O(n). Each insert/delete/reverse/range-sum uses a constant number of these operations. Building by repeated merge takes expected O(n log n) as a safe bound. Pool storage O(n_initial+insertions); recursion stack expected O(log n), worst O(n).

Example input and output

n q, n values; I p x inserts before 1-based p (p=length+1 appends), D p deletes, R l r reverses inclusive range, S l r prints its sum. n may be zero; deletion and range commands must reference existing positions. All sums fit long long.

Input

4 5
1 2 3 4
R 2 4
I 3 9
S 2 4
D 2
S 1 4

Output

16
15

After reversal and insertion the sequence is [1,4,9,3,2], so positions 2–4 sum to 16. Deleting position 2 leaves [1,9,3,2], totaling 15.

Practical applications

Sequence editors; interval reversals; cut-and-paste operations; dynamic indexed sums; maintaining sequences with insertions too frequent for vector shifting.

Check your understanding

Why must split push a reversal flag before descending?

Put it into practice

Add CUT l r p, moving a block before position p in the sequence remaining after removal.