Partial sums usage.

We have an array $A[1..N]$ with unknown values and a set of intervals $[L_i, R_i]$. For each interval we know sum $S_i$ of values in the array $A$ in the given range $[L_i, R_i]$.

So the question is to recover possible arrangement of numbers in the array $A$ without contradiction to the sums on the intervals.

I am wondering about solution which envolves usage of partial sums. Cause there is a solution for the task, when we have parity information instead of sums on the intervals.

This looks like just a system of linear equations in $N$ variables, so I'm not exactly sure what you're looking for, but here's a quick algorithm:
Let $\sigma[k]$ be the partial sum $A + \cdots + A[k]$, and let $\sigma = 0$. Then each interval $[L_i, R_i]$ gives the constraint $\sigma[R_i] - \sigma[L_i -1] = S_i$. So now we have a list of equations.
Working backwards from $k = N$ down to $k=1$, if in our list there are two or more equations of the form $\sigma[k] - \sigma[m] = s$, then we will rewrite the equations with small $m$ by cutting out the overlapping parts. For example, if we have \begin{align} \sigma - \sigma &= 4000 \\ \sigma - \sigma &= 5000\\ \sigma - \sigma &= 9000 \end{align} then we would replace the bottom two with \begin{align} \sigma - \sigma &= 5000 - 4000 = 1000\\ \sigma - \sigma &= 9000 - 5000 = 4000 \end{align} If we ever have two equations with the same left-hand-side expression $\sigma[k] - \sigma[m]$ but different right-hand-side values, then of course the constraints are unsatisfiable.
After that, we just work forwards from $A$ to $A[N]$. If when we get to $A[k]$ there is no equation in our list of the form $\sigma[k] - \sigma[m] = s$, then we just let $A[k] = 0$. Otherwise, there is exactly one equation of the form $\sigma[k] - \sigma[m] = s$, and since the values of $A$ through $A[k-1]$ are determined at this point, there exists exactly one value of $A[k]$ (namely, $s + \sigma[m] - \sigma[k-1]$) that will make the equation $\sigma[k] - \sigma[m] = s$ true. In this way assign all the $A[N]$.
• Oops, I made a small error; it's been corrected. Suppose we have $A + \cdots + A = 60$ and $A + \cdots + A = 220$. Then the algorithm gives $A = A = A = A = 0$; $A = 60$; $A = A = A = A = 0$; $A = 220 - 60 = 160$. – JohnJamesSmith Feb 6 '12 at 2:16