Oh, and while I'm sure mratsim already knows all this, because this is a thread about Nim and statistics and R and other things and most passers by/search results finers probably do not know this, it bears noting that these binary indexed sum trees are often the fastest way to compute things like medians or other quantiles or other order statistics over moving data windows, at least up to a certain precision aka number of bins.
Such CDF operations are almost the same as sampling without replacement. In both cases one is maintaining a CDF and/or its inverse as data comes & goes (with moving data windows the data both comes and goes while with sampling it only goes). With Wong/Fenwick/binary/Fibonacci/whatever decomposition indexed sum trees, the per-datum scaling becomes about the _alphabet size_ or precision **not** the window size. (There is always an overall O(N data points) factor for the whole data set not just each window.) By comparison, the R `runmed` implemented in `Srunmed.c`, for example, has atrocious `O(w)` scaling in window size `w`. `Srunmed.c`, while better than the _most_ naive sort-every-data-window-not-even-with-a-radix-sort `O(w*log(w))` is very poor work. It does not even do the binary-search-of-an-ordered-array-with-AVX-optimized-memmove adjustments which would be both simpler than what `Srunmed.c` already does and a significant constant factor speed up as well as generalizing to arbitrary quantiles. These index decomposition sum trees' (probably the most suggestive name) `w`-independence is even better unless you need too many bins. 64..256 KiBins is a lot of resolution and fits in L3 these days for even 8 byte counter sizes, though 4B or even 2B are often enough. This is obviously easier with the 2x space optimization I mentioned above. True full precision for index decomposition sum trees needs a bin for every possible number or say 2^32 bins for a `float32` which can get very memory intensive or require expensive-in-the-small sparse arrays/hashing. At loss of precision with numbers (as opposed to mratsim's words case), you can have some, e.g., exponentially spaced bin mapping from the full range to a more manageable amount. If you need full precision/exact answers then usually the best performer is a B-tree augmented to be an order statistics tree can get you "full precision" with `O(lg(w))` per datum scaling. Even a ranked binary search tree as per KnuthV3 in the late 1960s is better than R's `Srunmed.c`, though. `w` can easily be in the 1000s and N millions or more. So, R's current core impl is potentially leaving many orders of magnitude of performance on the table. Of course, people using R are rarely very sensitive to performance. /end-R-impls-a-lot-but-has-longstanding-poor-impls-of-even-basic-stuff-rant| ---|---
