Something I've found useful is being able to maintain a CDF over a sliding window of samples.

The way I've traditionally done it is with an augmented binary tree where I can easily compute the prefix sum of the sample values.

I'm not sure if there are any insights from that article that would allow me to do it better.