How to represent sums of piecewise quadratic functions for efficient optimisation? I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has a continuous compactly supported piecewise linear distribution of possible time allocations; the total contention at any time is then a certain sum of pairwise products of these individual piecewise linear distributions (this is the JointHeight criticality estimate, see [1]). As a consequence I am interested in the following:

Question: How can one represent sums of continuous compactly supported piecewise quadratic functions, in a way which affords efficient implementations of:


adding/removing/modifying a summand,
finding the maximum.


As D.W. points out, if a summand that is added/removed/modified spans the whole domain of support of the sum, then it seems inevitable to need to traverse the whole thing. However, when that domain is rather smaller, I'd hope to be able to efficiently update the whole sum without incurring an $\textrm{O}(\#\textrm{Tasks})$ cost; I should only need to update the control points that overlap the domain of the modified task.    

After making each search decision, constraint solving takes place, resulting in the modification of the availabilities of certain tasks. My goal is to be able to efficiently update the above representation with these modifications, so that one can efficiently recompute the new time which is under maximum contention after these updates.    

Now, a sum of continuous compactly supported piecewise quadratic functions is itself continuous, compactly supported and piecewise quadratic. Once one has an explicit piecewise quadratic expression, it is straightforward to compute the maximum. However I haven't figured out an implementation which would allow me to efficiently recompute the control points when adding/removing/modifying a summand.    

A point of comparison is the PiecewiseExpand function from Mathematica. PiecewiseExpand can take a sum of piecewise functions and return an explicit piecewise expression, with the minimal number of control points. So I'd be interested in knowing how such a function is implemented.    

[1] Beyond Contention: Extending Texture-Based Scheduling Heuristics (1997, AAAI'97/IAAI'97).
J. Christopher Beck, Andrew J. Davenport, Edward M. Sitarski, Mark S. Fox
I'd suggest storing this in a tree data structure.  The tree represents a piecewise quadratic function (namely, the sum), and each leaf of the tree represents the domain of one of the pieces.  Each internal node corresponds to a range of intervals (the union of the intervals associated with the leaves under it).  Store in each node the maximum of the function on that interval.  Also, you will store in each node some of the summands (each of which is a quadratic function on some limited domain).  The quadratic function associated with a leaf is the sum of all of the summands found on the path from the root to that leaf.

If you maintain the tree using a self-balancing binary tree data structure, the height of the tree will be $O(\log n)$, where $n$ is the number of pieces in the sum.

Now, suppose you want to update the tree by adding a quadratic function $f$ with a small domain.  First, split the two leaves $f$'s endpoints fall into, if necessary.  Then, you can express the domain of $f$ as a union of $O(\log n)$ intervals, each associated with one of the nodes of the tree.  So, update those $O(\log n)$ nodes by adding in $f$ as another summand.  Also, for each leaf whose interval is contained in the domain of $f$, compute the maximum value of the quadratic function that leaf represents.  Now propagate these maxima up the tree, until you have eventually updated the maximum at the root; this lets you compute the maximum of the sum.  If the domain of $f$ contains $m$ leaves, then the running time for this update will be $O(m + \log n)$.  So, it will be quite slow if the domain of $f$ is large, but it will be fast if the domain of $f$ is very small.

I could not figure out how to make this run in $O(\log n)$ time regardless of the size of the domain of the summand added.

I suspect there may be a simpler data structure that also achieves $O(m + \log n)$ time updates -- I suspect the machinery of self-balancing binary tree isn't needed.