I have a an array of intervals [a,b] (where [a,b] = set of all x such that a<=x<=b). Each one of these intervals has a value associated with it (think of it as the cost of something across such interval). Intervals can overlap. Intervals are dynamic (they can be added, removed, translated, and their size can be changed). Also, the value associated with any of such intervals can change.
I need to create a graph containing the sum of all such values across interval [start, end] which is defined as the interval containing all of such intervals. In order to do so I need an ordered list of where, along the real line, such values change, as well as what values they are changing between. Such list needs to be easily / quickly updated when an interval in the original array changes.
Side notes: assume not very large number of intervals (hundreds?).
Any suggestions on data structures / algorithms to do this effectively?
