The non-rotating Treap, commonly referred to as the FHQ-Treap, operates without the rotation mechanisms found in traditional Treaps or AVL trees. Its equilibrium is maintained exclusively through deterministic split and merge procedures, combined with randomly assigned priority values. This architecture inherently supports persistent data structure patterns because every modification produces new root references rather than altering existing nodes in place.

Core Mechanism: Split and Merge

The entire structure revolves around two primitives. The split operation partitions a given tree into two separate trees based on a specific criterion, typically node values or implicit indices. Conversely, merge combines two independent trees into a single valid structure, assuming all elements in the first tree satisfy an ordering constraint relative to the second. Each node stores a randomized priority that dictates its position in the underlying min-heap, guaranteeing expected logarithmic height.

Value-Based Partitioning

When dividing by value, the algorithm traverses the current root against a target threshold. If the root's data falls within the left partition boundary, it attaches to the smaller subset, and the operation recurses on the right child. Otherwise, the root joins the larger subset, directing recursion toward the left child. Size metrics are recalculated upon stack unwinding to preserve subtree statistics.

void partition_tree(int root, int limit, int &out_left, int &out_right) {
    if (!root) { out_left = out_right = 0; return; }
    
    apply_lazy_reverse(root);

    if (memory_pool[root].data_val <= limit) {
        out_left = root;
        partition_tree(memory_pool[root].right_child, limit, memory_pool[root].right_child, out_right);
    } else {
        out_right = root;
        partition_tree(memory_pool[root].left_child, limit, out_left, memory_pool[root].left_child);
    }
    refresh_statistics(root);
}

Tree Unification

Merging requires two conditions: valid tree roots and a strict value partition between them. The function compares root priorities to determine ancestry. A higher priority elevates the node to the parent position. Depending on the outcome, the child pointer is updated recursively. One branch must always align with the merging condition to prevent structural violations.

int unite_subtrees(int left_root, int right_root) {
    if (!left_root || !right_root) return left_root + right_root;

    apply_lazy_reverse(left_root);
    apply_lazy_reverse(right_root);

    if (memory_pool[left_root].rand_priority > memory_pool[right_root].rand_priority) {
        memory_pool[left_root].right_child = unite_subtrees(memory_pool[left_root].right_child, right_root);
        refresh_statistics(left_root);
        return left_root;
    } else {
        memory_pool[right_root].left_child = unite_subtrees(left_root, memory_pool[right_root].left_child);
        refresh_statistics(right_root);
        return right_root;
    }
}

Fundamental Operations

Insertion Protocol

Introducing a new element requires isolating the insertion point dynamically. The global tree splits at the incoming value. A fresh node is allocated, then stitched back together via sequential merges. The resulting structure preserves both binary search properties and heap constraints.

void inject_value(int val) {
    int part_a, part_b;
    partition_tree(tree_root, val, part_a, part_b);
    
    int new_el_id = alloc_node(val);
    tree_root = unite_subtrees(unite_subtrees(part_a, new_el_id), part_b);
}

Deletion Workflow

Removing an instance involves double-splitting. First, partition the tree at the target value. Then, split the lower bound segment at target - 1. The middle segment now contains only instances of the target value. Eliminating the root of this middle segment effectively removes one occurrence. Its children are merged, and the three segments recombine.

void purge_value(int val) {
    int s1, s2, s3;
    partition_tree(tree_root, val, s1, s3);
    partition_tree(s1, val - 1, s1, s2);
    
    s2 = unite_subtrees(memory_pool[s2].left_child, memory_pool[s2].right_child);
    tree_root = unite_subtrees(unite_subtrees(s1, s2), s3);
}

Ranking and Selection

Determining the rank of a specific value follows the same split pattern. Partitioning at value - 1 isolates all strictly smaller elements in the left branch. Adding one yields the exact rank. Merging restores integrity immediately afterward.

Retrieving the k-th smallest number bypasses splitting entirely. An iterative descent calculates positions based on left-subtree sizes. If the rank matches the left size plus one, the current node holds the answer. Otherwise, traversal proceeds left or adjusts the rank counter accordingly before moving right.

int fetch_kth_element(int rank_target) {
    int curr = tree_root;
    while (curr) {
        apply_lazy_reverse(curr);
        int left_count = memory_pool[memory_pool[curr].left_child].subtree_size;
        if (left_count + 1 == rank_target) return memory_pool[curr].data_val;
        if (rank_target <= left_count) curr = memory_pool[curr].left_child;
        else { rank_target -= (left_count + 1); curr = memory_pool[curr].right_child; }
    }
    return INT_MIN;
}

Boundary Queries

Predecessor queries identify the largest value strictly below a threshold. After splitting at value - 1, the maximum element resides at the farthest right descent of the left component. Successor queries mirror this logic, targeting the extreme left path of the right component following a split at the exact threshold.

Implicit Index Variation and Range Modifications

When managing linear sequences rather than arbitrary numeric domains, the splitting criterion shifts from data values to subtree depths (implicit keys). Each leaf represents a sequential index. Splitting by size isolates contiguous ranges. This variant enables efficient range updates via lazy propagation tags. For instance, reversing a subsegment [l, r] requires extracting the interval into a separate subtree, toggling a flip flag on its root, and seamlessly merging the components back into the primary structrue. In-order traversal subsequently reflects the modified order.

Complete Reference Implementation

The following C++ module consolidates the previously described algorithms. It utilizes a static memory pool, renames internal structures for clarity, and implements both standard value-based operations and implicit-index manipulation. Control flow has been optimized for readability and modular execution.

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <climits>

using namespace std;

const int MAX_NODES = 100005;

struct TreapNode {
    int left_child, right_child;
    int data_val;
    unsigned rand_priority;
    int subtree_size;
    bool lazy_flip;

    TreapNode() : left_child(0), right_child(0), data_val(0), 
                  rand_priority(0), subtree_size(1), lazy_flip(false) {}
};

TreapNode memory_pool[MAX_NODES];
int pool_allocator_idx = 0;
int tree_root = 0;

inline int alloc_node(int val) {
    ++pool_allocator_idx;
    memory_pool[pool_allocator_idx] = TreapNode();
    memory_pool[pool_allocator_idx].data_val = val;
    memory_pool[pool_allocator_idx].rand_priority = rand();
    return pool_allocator_idx;
}

inline void refresh_statistics(int idx) {
    memory_pool[idx].subtree_size = memory_pool[memory_pool[idx].left_child].subtree_size +
                                    memory_pool[memory_pool[idx].right_child].subtree_size + 1;
}

inline void apply_lazy_reverse(int idx) {
    if (!idx || !memory_pool[idx].lazy_flip) return;
    swap(memory_pool[idx].left_child, memory_pool[idx].right_child);
    memory_pool[memory_pool[idx].left_child].lazy_flip ^= true;
    memory_pool[memory_pool[idx].right_child].lazy_flip ^= true;
    memory_pool[idx].lazy_flip = false;
}

void partition_tree(int root, int limit, int &out_left, int &out_right) {
    if (!root) { out_left = out_right = 0; return; }
    
    apply_lazy_reverse(root);

    if (memory_pool[root].data_val <= limit) {
        out_left = root;
        partition_tree(memory_pool[root].right_child, limit, memory_pool[root].right_child, out_right);
    } else {
        out_right = root;
        partition_tree(memory_pool[root].left_child, limit, out_left, memory_pool[root].left_child);
    }
    refresh_statistics(root);
}

int unite_subtrees(int left_root, int right_root) {
    if (!left_root || !right_root) return left_root + right_root;

    apply_lazy_reverse(left_root);
    apply_lazy_reverse(right_root);

    if (memory_pool[left_root].rand_priority > memory_pool[right_root].rand_priority) {
        memory_pool[left_root].right_child = unite_subtrees(memory_pool[left_root].right_child, right_root);
        refresh_statistics(left_root);
        return left_root;
    } else {
        memory_pool[right_root].left_child = unite_subtrees(left_root, memory_pool[right_root].left_child);
        refresh_statistics(right_root);
        return right_root;
    }
}

void inject_value(int val) {
    int part_a, part_b;
    partition_tree(tree_root, val, part_a, part_b);
    tree_root = unite_subtrees(unite_subtrees(part_a, alloc_node(val)), part_b);
}

void purge_value(int val) {
    int s1, s2, s3;
    partition_tree(tree_root, val, s1, s3);
    partition_tree(s1, val - 1, s1, s2);
    s2 = unite_subtrees(memory_pool[s2].left_child, memory_pool[s2].right_child);
    tree_root = unite_subtrees(unite_subtrees(s1, s2), s3);
}

int compute_rank(int val) {
    int part_x, part_y;
    partition_tree(tree_root, val - 1, part_x, part_y);
    int result = memory_pool[part_x].subtree_size + 1;
    tree_root = unite_subtrees(part_x, part_y);
    return result;
}

int reverse_segment_l_r(int l, int r) {
    // Helper for sequence reversal example
    int alpha, beta, gamma;
    partition_by_index(tree_root, l - 1, alpha, beta);
    partition_by_index(beta, r - l + 1, beta, gamma);
    memory_pool[beta].lazy_flip ^= true;
    tree_root = unite_subtrees(unite_subtrees(alpha, beta), gamma);
    return 0;
}

void traverse_print(int idx) {
    if (!idx) return;
    apply_lazy_reverse(idx);
    traverse_print(memory_pool[idx].left_child);
    printf("%d ", memory_pool[idx].data_val);
    traverse_print(memory_pool[idx].right_child);
}

int main() {
    srand(time(nullptr));
    int query_count;
    scanf("%d", &query_count);

    while (query_count--) {
        int op, input_val;
        scanf("%d %d", &op, &input_val);

        switch(op) {
            case 1: inject_value(input_val); break;
            case 2: purge_value(input_val); break;
            case 3: printf("%d\n", compute_rank(input_val)); break;
            case 4: printf("%d\n", fetch_kth_element(input_val)); break;
            case 5: {
                int la, lb;
                partition_tree(tree_root, input_val - 1, la, lb);
                int pred = input_val;
                int tmp = la;
                while(memory_pool[tmp].right_child) tmp = memory_pool[tmp].right_child;
                pred = memory_pool[tmp].data_val;
                tree_root = unite_subtrees(la, lb);
                printf("%d\n", pred); break;
            }
            default: {
                int ra, rb;
                partition_tree(tree_root, input_val, ra, rb);
                int succ = input_val;
                int tmp = rb;
                while(memory_pool[tmp].left_child) tmp = memory_pool[tmp].left_child;
                succ = memory_pool[tmp].data_val;
                tree_root = unite_subtrees(ra, rb);
                printf("%d\n", succ); break;
            }
        }
    }
    return 0;
}