Competitive Programming - Balanced Trees Related Topics

Treap ATTENTION: Out the door and to the left. https://caterpillow.github.io/byot Thanks meow. AKA Cartesian Tree, Randomized BST; supports $log n$ insertion, deletion, lookup and closure operations (push_up) https://cp-algorithms.com/data_structures/treap.html https://oi.baoshuo.ren/fhq-treap A. std::set class containers template<typename T> struct treap { struct node { T key; ll priority; ll l, r; // push_up maintains ll size; }; vector<node> tree; vec free_list; private: void push_up(ll o) { tree[o].size = tree[tree[o].l].size + tree[tree[o].r].size + 1; } II split_by_value(ll o, T const& key) { // 偏序 [<, >=] if (!...

December 26, 2024 · 4 min · 816 words · mos9527