← all categories

Treap Implicit c5616e40

Implicit (positional) treap: array-as-balanced-BST via randomized split/merge by subtree size. Supports insert-at-position, range reverse, and an "op" block (aggregate + lazy tag) you swap for the problem at hand — default is range-add + range-sum. To change the op: edit Node's val/agg/lazy fields and comb()/apply() only; split/merge/push/pull never need to change. T needs operator+ and a default zero. Multi-page exception to the line budget.

Time: O(\log n) expected per operation. tested

content/data-structures/treap-implicit.h

template <typename T>
struct ImplicitTreap {
    struct Node {
        // ---- op: edit for a different aggregate/lazy tag ----
        T val, agg;
        T lazy = T();
        // ---- end op ----
        int l = -1, r = -1, sz = 1, rev = 0;
    };
    vector<Node> pool;
    mt19937 rng{random_device{}()};
    int root = -1;

    T comb(T a, T b) { return a + b; }  // op: combine two subtree aggregates
    void apply(int n, T v) { pool[n].val += v; pool[n].agg += v * pool[n].sz; pool[n].lazy += v; }  // op: push a lazy tag onto n

    int getSz(int n) { return n == -1 ? 0 : pool[n].sz; }
    T getAgg(int n) { return n == -1 ? T() : pool[n].agg; }
    int make(T x) { pool.push_back({x, x}); return (int)pool.size() - 1; }

    void pull(int n) {
        pool[n].sz = 1 + getSz(pool[n].l) + getSz(pool[n].r);
        pool[n].agg = comb(comb(getAgg(pool[n].l), pool[n].val), getAgg(pool[n].r));
    }

    void push(int n) {
        if (pool[n].rev) {
            swap(pool[n].l, pool[n].r);
            if (pool[n].l != -1) pool[pool[n].l].rev ^= 1;
            if (pool[n].r != -1) pool[pool[n].r].rev ^= 1;
            pool[n].rev = 0;
        }
        if (pool[n].lazy != T()) {
            if (pool[n].l != -1) apply(pool[n].l, pool[n].lazy);
            if (pool[n].r != -1) apply(pool[n].r, pool[n].lazy);
            pool[n].lazy = T();
        }
    }

    int merge(int l, int r) {
        if (l == -1) return r;
        if (r == -1) return l;
        push(l); push(r);
        if ((rng() % (unsigned)(getSz(l) + getSz(r))) < (unsigned)getSz(l)) {
            pool[l].r = merge(pool[l].r, r);
            pull(l);
            return l;
        } else {
            pool[r].l = merge(l, pool[r].l);
            pull(r);
            return r;
        }
    }

    void split(int n, int k, int &l, int &r) {  // first k elements go to l
        if (n == -1) { l = r = -1; return; }
        push(n);
        if (k <= getSz(pool[n].l)) {
            split(pool[n].l, k, l, pool[n].l);
            r = n;
        } else {
            split(pool[n].r, k - getSz(pool[n].l) - 1, pool[n].r, r);
            l = n;
        }
        pull(n);
    }

    void insert(int pos, T x) {  // 0-indexed
        int l, r; split(root, pos, l, r);
        root = merge(merge(l, make(x)), r);
    }

    void reverse(int lo, int hi) {  // inclusive [lo, hi], 0-indexed
        int l, m, r;
        split(root, lo, l, m);
        split(m, hi - lo + 1, m, r);
        pool[m].rev ^= 1;
        root = merge(merge(l, m), r);
    }

    void update(int lo, int hi, T v) {  // inclusive [lo, hi]
        int l, m, r;
        split(root, lo, l, m);
        split(m, hi - lo + 1, m, r);
        apply(m, v);
        root = merge(merge(l, m), r);
    }

    T query(int lo, int hi) {  // inclusive [lo, hi]
        int l, m, r;
        split(root, lo, l, m);
        split(m, hi - lo + 1, m, r);
        T res = getAgg(m);
        root = merge(merge(l, m), r);
        return res;
    }
};