Some here are questioning the motivation of this data structure. It is well motivated at least in the context of time series. We (almost) all learn 2 things a

Some here are questioning the motivation of this data structure. It is well motivated at least in the context of time series. We (almost) all learn 2 things at very young ages: 1) the world changes and 2) even one wild point can pollute an average. In time series contexts, we also learn early solutions to 1) a moving data window (flat or fancily weighted over time) and 2) percentiles/quantiles/order statistics are more robust. Combining the two solutions means you want to efficiently delete old/insert new/query quantiles over moving data windows. If you need multiple (e.g. 1%, 25%, median, 75%, 99% is a classic case) and exact quantiles over large data windows (in numbers of points), a counted B-tree is about as good as you can do, and can be many orders of magnitude less work than more naive solutions (which absolutely show up In The Wild - I have personally seen them many times). There is a case that article does not address when you have many-way ties aka many duplicate keys, but that can be handled within the same general framework. If you know something about the dynamic range of your data then you can also get more approximate dynamic quantiles with a histogram with log/exp-spaced bins (like floats) with counters backed by a Fenwick Tree (to make both PDF & CDF updates efficient). You can further boost accuracy with Parzen mid-quantile interpolation. A fully worked example in Nim is at https://github.com/c-blake/adix/blob/master/adix/lghisto.nim https://github.com/c-blake/adix/blob/master/adix/lghisto.nim In the same github repo there is also a Nim implemention of counted B-trees (though it is harder to use).