For those interested in reading more about this idea, the term is "monoid cached trees". The Fenwick tree is a particular well-known special case. (I looked in

For those interested in reading more about this idea, the term is "monoid cached trees". The Fenwick tree is a particular well-known special case. (I looked into monoid cached trees for float placement in CSS at one point in an effort to come up with an O(n log n) algorithm. I succeeded, but the constant factor was so high that it wasn't worth the price. I ended up switching to an algorithm based on splay trees that, while O(n^2) in the worst case, ended up being O(n) with a small constant factor on real-world pages.)