This approach is essentially what is called an "augmented data structure". Namely, in this case a B-tree is augmented to store an element count. But there are o

This approach is essentially what is called an "augmented data structure". Namely, in this case a B-tree is augmented to store an element count. But there are obviously many other data structures to which this can be applied, and many types of additional values that can be stored. https://www.geeksforgeeks.org/introduction-to-augmented-data-structure/ https://www.geeksforgeeks.org/introduction-to-augmented-data... https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/10-augmentedTrees/augtrees.pdf https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/fall09/... https://www.cs.toronto.edu/~tabrown/csc263/2014W/week4.interval.pdf https://www.cs.toronto.edu/~tabrown/csc263/2014W/week4.inter...