A tree of ranges over an array: range sums or minimums, point updates and range adds in O(log n), with lazy tags that put work off until a query needs it.
This interactive visualization needs JavaScript.