Treap (Cartesian Tree)

> Maintaining the sizes of subtrees

Something that's not mentioned in that article is that you can maintain any monoid efficiently over balanced trees, not just the subtree size (aka you need an identity element and an associative operation). Most widely known monoids are boring, but there are more interesting monoids. Interval trees can be implemented as an augmentation using a monoid (this concept is more widely known as augmenting a tree). Range min max augmentations can be used to implement succinct trees (this comes from Sadakane's work on succinct trees, he didn't describe it as a monoid IIRC, but it turns out it is one).

By looking at it from a monoid angle, the specific balanced tree can be abstracted away. Treaps are VERY easy to implement, but the monoids apply to any n-ary balanced trees. There was an article a few days ago about very efficient B-Trees, but from what I've seen they did not support general purpose augmentations, probably because the implementation would have to be partially evaluated to be optimal while being general.

In any case, cool stuff and totally under-explored in my opinion. I hope LLMs will help us become optimal in this area one day and help us automatically select an optimal augmentation and balanced tree. There are so many problems that can be sped up by balanced trees and augmentations.

> Treaps have been proposed by Raimund Siedel and Cecilia Aragon in 1989.

The correct name is Raimund Seidel https://en.wikipedia.org/wiki/Raimund_Seidel

The primary attraction of treaps (aside from fast intersection/union/diff) is that they are probably one of the easiest types of balanced trees that can be implemented manually if you need a dependency-free balanced tree. There are only two types of rotations, they are straightforward, and they are mirror images of each other.

These days, where an agent can just write you an AVL tree, red-black tree, or B-tree library in under a minute, it probably matters less.

A very nice problem solved using treap: https://stackoverflow.com/questions/79751600/solve-cses-moun...

this is non-rotation treap (fhq treap), it is more common among competitive programming folks, for other cs folks, i believe the rotating variant is more popular: https://www.cs.umd.edu/class/spring2022/cmsc420-0101/Lects/l...

Yeah