A short-ish example of incremental & lazy alternative to Array#reduce
when you have a bunch of rapidly changing values.
The basic idea is to use a normal array and push values to it, but also think of the array as a representation of a binary tree (using the scheme outlined in Wikipedia). Each tree node keeps track of the reduced value of the subtree under it, and whenever something changes (i.e. a value is pushed to the array, a value is removed etc.) the changed node and its ancestors are marked to be "dirty", i.e. needing recalculation. All the dirty nodes get refreshed lazily when the reduced value for the tree is needed.
Each single tree modification marks at most 2 * log N nodes dirty (where N is the number of nodes in the tree). Therefore calculating the reduced value takes at O(min(m log N, N)) time (where m is the number of single modifications done to the tree since the last time the reduced value was calculated), assuming the given red