Build Lab: Left-Leaning Red-Black (LLRB) Order-Statistic Tree with rank and select

Architectural Synthesis: LLRB Rebalancing + Subtree Size Invariant

Let us trace how sz (subtree node count) interacts with the three LLRB primitive transformations:

1. rotateLeft(h) (promotes $x = h.\text{right}$ above $h$): Before rotation, $h$ was the root of the local subtree; after rotation, $x$ is the root of the exact same set of nodes! Therefore, we set x->sz = h->sz and recompute h->sz = 1 + size(h->left) + size(h->right) in $O(1)$ time.
2. rotateRight(h) (promotes $x = h.\text{left}$ above $h$): Symmetric—set x->sz = h->sz and recompute h->sz = 1 + size(h->left) + size(h->right).
3. flipColors(h): Only flips boolean color bits without changing any parent-child links, so all sz fields remain untouched!

With sz maintained at every node, we unlock three $O(\log N)$ analytical queries:

• rank(key): Returns the exact number of elements in the set strictly less than key ($|\{x \in S : x < \text{key}\}|$).
• select(k) ($0 \le k < N$): Returns the unique key $x \in S$ whose rank(x) == k.
• rangeCount(lo, hi) ($lo \le hi$): Returns the number of keys in the closed interval $[lo, hi]$ in $O(\log N)$ time via rank(hi) - rank(lo) + (contains(hi) ? 1 : 0)!

Production Reference Implementation: Complete LLRB Order-Statistic Tree

// C++20: Complete Left-Leaning Red-Black (LLRB) Order-Statistic Tree
#include <cstdint>
#include <cassert>

template <typename Key>
class LLRBOrderStatisticTree {
    struct Node {
        Key key;
        int32_t sz = 1;
        bool red = true;
        Node *left = nullptr, *right = nullptr;
        explicit Node(Key k) : key(k) {}
    };

    Node* root = nullptr;

    static bool isRed(const Node* u) noexcept { return u != nullptr && u->red; }
    static int32_t size(const Node* u) noexcept { return u ? u->sz : 0; }
    static void pull(Node* u) noexcept { u->sz = 1 + size(u->left) + size(u->right); }

    static Node* rotateLeft(Node* h) noexcept {
        Node* x = h->right;
        h->right = x->left;
        x->left = h;
        x->red = h->red;
        h->red = true;
        x->sz = h->sz; // x replaces h as root of this exact subtree
        pull(h);        // Recompute demoted node h
        return x;
    }

    static Node* rotateRight(Node* h) noexcept {
        Node* x = h->left;
        h->left = x->right;
        x->right = h;
        x->red = h->red;
        h->red = true;
        x->sz = h->sz;
        pull(h);
        return x;
    }

    static void flipColors(Node* h) noexcept {
        h->red = !h->red;
        h->left->red = !h->left->red;
        h->right->red = !h->right->red;
    }

    static Node* insertRec(Node* h, const Key& key) {
        if (!h) return new Node(key);
        if (key < h->key)      h->left  = insertRec(h->left, key);
        else if (h->key < key) h->right = insertRec(h->right, key);

        if (isRed(h->right) && !isRed(h->left))      h = rotateLeft(h);
        if (isRed(h->left)  && isRed(h->left->left))  h = rotateRight(h);
        if (isRed(h->left)  && isRed(h->right))       flipColors(h);

        pull(h);
        return h;
    }

public:
    int32_t size() const noexcept { return size(root); }

    void insert(const Key& key) {
        root = insertRec(root, key);
        root->red = false; // Root is always Black
    }

    bool contains(const Key& key) const noexcept {
        const Node* u = root;
        while (u) {
            if (key < u->key)      u = u->left;
            else if (u->key < key) u = u->right;
            else return true;
        }
        return false;
    }

    // Number of keys strictly less than 'key' in O(log N) time
    int32_t rank(const Key& key) const noexcept {
        const Node* u = root;
        int32_t count = 0;
        while (u) {
            if (key < u->key) {
                u = u->left;
            } else if (u->key < key) {
                count += 1 + size(u->left);
                u = u->right;
            } else {
                return count + size(u->left);
            }
        }
        return count;
    }

    // 0-indexed k-th smallest key in O(log N) time
    const Key& select(int32_t k) const noexcept {
        assert(k >= 0 && k < size(root));
        const Node* u = root;
        while (u) {
            int32_t leftSz = size(u->left);
            if (k == leftSz) return u->key;
            if (k < leftSz) {
                u = u->left;
            } else {
                k -= (leftSz + 1);
                u = u->right;
            }
        }
        return root->key;
    }

    // Count of keys in closed interval [lo, hi] in O(log N) time
    int32_t rangeCount(const Key& lo, const Key& hi) const noexcept {
        if (hi < lo) return 0;
        return rank(hi) - rank(lo) + (contains(hi) ? 1 : 0);
    }
};