Overview

The FHQ Treap (also known as the Non-Rotational Treap) is a type of randomized binary search tree. Unlike standard AVL or Splay trees that rely on rotations to maintain balance, the FHQ Treap utilizes two fundamental operations: split and merge. By assigning random priorities to nodes, the tree structure maintains the properties of a Binary Search Tree (BST) based on node values while maintaining a heap structure based on priorities. This approach is often preferred for its simplicity in implementation and ability to handle sequence splitting and merging efficiently.

Node Structure

Each node in the tree stores pointers to its children, the value it holds, a randomly generated priority for balancing, and the size of the subtree rooted at that node.

const int MAX_NODES = 100005;
std::mt19937 rng(1337);

struct TreapNode {
    int lChild, rChild;
    int value, priority;
    int subtreeSize;
} tree[MAX_NODES];

int rootIndex = 0;
int nodeCount = 0;

Basic Operations

Update Utility

This helper function recalculates the subtree size for a given node based on its children. It must be called whenever the structure of a subtree changes.

void pushUp(int id) {
    tree[id].subtreeSize = tree[tree[id].lChild].subtreeSize + tree[tree[id].rChild].subtreeSize + 1;
}

Create Node

Allocates a new node from the static pool, initializes its fields, and returns its index.

int createNode(int val) {
    int newNode = ++nodeCount;
    tree[newNode].value = val;
    tree[newNode].priority = rng();
    tree[newNode].subtreeSize = 1;
    tree[newNode].lChild = tree[newNode].rChild = 0;
    return newNode;
}

Split

The split operation divides a tree into two separate trees. We split the tree rooted at currentNode by a threshold value. The left tree (returned via leftPart) contains nodes with values less than or equal to the threshold, and the right tree (returned via rightPart) contains nodes with values greater than the threshold.

void split(int currentNode, int threshold, int& leftPart, int& rightPart) {
    if (!currentNode) {
        leftPart = rightPart = 0;
        return;
    }
    if (tree[currentNode].value <= threshold) {
        leftPart = currentNode;
        split(tree[currentNode].rChild, threshold, tree[currentNode].rChild, rightPart);
    } else {
        rightPart = currentNode;
        split(tree[currentNode].lChild, threshold, leftPart, tree[currentNode].lChild);
    }
    pushUp(currentNode);
}

Merge

The merge operation combines two trees, treeA and treeB, into a single tree. It assumes that all values in treeA are less than all values in treeB. The operation uses the priority to decide which root becomes the parent of the other.

int merge(int treeA, int treeB) {
    if (!treeA || !treeB) return treeA + treeB;
    
    if (tree[treeA].priority > tree[treeB].priority) {
        tree[treeA].rChild = merge(tree[treeA].rChild, treeB);
        pushUp(treeA);
        return treeA;
    } else {
        tree[treeB].lChild = merge(treeA, tree[treeB].lChild);
        pushUp(treeB);
        return treeB;
    }
}

Core Functionalities

Insertion

To insert a value, we first split the tree into the left part (values $\le$ new value) and right part (values > new value). We create a new node and then merge the left part, the new node, and the right part in order.

void insertValue(int val) {
    int x, y;
    split(rootIndex, val, x, y);
    rootIndex = merge(merge(x, createNode(val)), y);
}

Deletion

To delete a value, we split the tree to isolate the target value. First, we split at val to get $\le$ and $>$. Then we split the $\le$ part at val-1 to get $<$ and $=$. The root of the tree containing values equal to val is the node to be removed. We merge its children (which discards the root) and merge the remaining trees back together.

void deleteValue(int val) {
    int x, y, z;
    split(rootIndex, val, x, z);
    split(x, val - 1, x, y);
    // y is the tree containing nodes equal to val
    y = merge(tree[y].lChild, tree[y].rChild); 
    rootIndex = merge(merge(x, y), z);
}

Rank Query

Finds the rank of a value (the number of elements less than it plus one). We split the tree at val - 1. The size of the resulting left tree plus one is the rank.

int getRank(int val) {
    int x, y;
    split(rootIndex, val - 1, x, y);
    int result = tree[x].subtreeSize + 1;
    rootIndex = merge(x, y);
    return result;
}

K-th Number Query

Finds the value at a specific rank. We traverse the tree from the root, comparing the desired rank with the size of the left subtree to decide whether to go left or right.

int getValueByRank(int rank) {
    int current = rootIndex;
    while (current) {
        int leftSize = tree[tree[current].lChild].subtreeSize;
        if (leftSize + 1 == rank) {
            return tree[current].value;
        } else if (leftSize >= rank) {
            current = tree[current].lChild;
        } else {
            rank -= (leftSize + 1);
            current = tree[current].rChild;
        }
    }
    return 0; // Should not be reached if rank is valid
}

Predecessor

Finds the largest value strictly less than val. We split the tree at val - 1. The predecessor is the maximum value (rightmost node) in the left part.

int getPredecessor(int val) {
    int x, y;
    split(rootIndex, val - 1, x, y);
    int current = x;
    while (tree[current].rChild) {
        current = tree[current].rChild;
    }
    rootIndex = merge(x, y);
    return tree[current].value;
}

Successor

Finds the smallest value strictly greater than val. We split the tree at val. The successsor is the minimum value (leftmost node) in the right part.

int getSuccessor(int val) {
    int x, y;
    split(rootIndex, val, x, y);
    int current = y;
    while (tree[current].lChild) {
        current = tree[current].lChild;
    }
    rootIndex = merge(x, y);
    return tree[current].value;
}

Complete Implementation

#include <iostream>
#include <random>

using namespace std;

const int MAX_NODES = 100005;
std::mt19937 rng(1337);

struct FHQTreap {
    struct Node {
        int lChild, rChild;
        int value, priority;
        int subtreeSize;
    } pool[MAX_NODES];

    int root, count;

    FHQTreap() : root(0), count(0) {}

    void pushUp(int id) {
        pool[id].subtreeSize = pool[pool[id].lChild].subtreeSize + pool[pool[id].rChild].subtreeSize + 1;
    }

    int createNode(int val) {
        int newNode = ++count;
        pool[newNode].value = val;
        pool[newNode].priority = rng();
        pool[newNode].subtreeSize = 1;
        pool[newNode].lChild = pool[newNode].rChild = 0;
        return newNode;
    }

    void split(int currentNode, int threshold, int& leftPart, int& rightPart) {
        if (!currentNode) {
            leftPart = rightPart = 0;
            return;
        }
        if (pool[currentNode].value <= threshold) {
            leftPart = currentNode;
            split(pool[currentNode].rChild, threshold, pool[currentNode].rChild, rightPart);
        } else {
            rightPart = currentNode;
            split(pool[currentNode].lChild, threshold, leftPart, pool[currentNode].lChild);
        }
        pushUp(currentNode);
    }

    int merge(int treeA, int treeB) {
        if (!treeA || !treeB) return treeA + treeB;
        if (pool[treeA].priority > pool[treeB].priority) {
            pool[treeA].rChild = merge(pool[treeA].rChild, treeB);
            pushUp(treeA);
            return treeA;
        } else {
            pool[treeB].lChild = merge(treeA, pool[treeB].lChild);
            pushUp(treeB);
            return treeB;
        }
    }

    void insert(int val) {
        int x, y;
        split(root, val, x, y);
        root = merge(merge(x, createNode(val)), y);
    }

    void erase(int val) {
        int x, y, z;
        split(root, val, x, z);
        split(x, val - 1, x, y);
        y = merge(pool[y].lChild, pool[y].rChild);
        root = merge(merge(x, y), z);
    }

    int getRank(int val) {
        int x, y;
        split(root, val - 1, x, y);
        int res = pool[x].subtreeSize + 1;
        root = merge(x, y);
        return res;
    }

    int getValueByRank(int rank) {
        int curr = root;
        while (curr) {
            int leftSize = pool[pool[curr].lChild].subtreeSize;
            if (leftSize + 1 == rank) return pool[curr].value;
            if (leftSize >= rank) curr = pool[curr].lChild;
            else {
                rank -= (leftSize + 1);
                curr = pool[curr].rChild;
            }
        }
        return 0;
    }

    int getPredecessor(int val) {
        int x, y;
        split(root, val - 1, x, y);
        int curr = x;
        while (pool[curr].rChild) curr = pool[curr].rChild;
        root = merge(x, y);
        return pool[curr].value;
    }

    int getSuccessor(int val) {
        int x, y;
        split(root, val, x, y);
        int curr = y;
        while (pool[curr].lChild) curr = pool[curr].lChild;
        root = merge(x, y);
        return pool[curr].value;
    }
} treap;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int q;
    cin >> q;
    while (q--) {
        int opt, val;
        cin >> opt >> val;
        switch (opt) {
            case 1: treap.insert(val); break;
            case 2: treap.erase(val); break;
            case 3: cout << treap.getRank(val) << "\n"; break;
            case 4: cout << treap.getValueByRank(val) << "\n"; break;
            case 5: cout << treap.getPredecessor(val) << "\n"; break;
            case 6: cout << treap.getSuccessor(val) << "\n"; break;
        }
    }
    return 0;
}