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.
 A: 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[1] + \cdots + A[k]$, and let $\sigma[0] = 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[10] - \sigma[7]  &= 4000 \\
\sigma[10] - \sigma[5]  &= 5000\\
\sigma[10] - \sigma[4]  &= 9000
\end{align}$$
then we would replace the bottom two with
$$\begin{align}
\sigma[7] - \sigma[5]  &= 5000 - 4000 = 1000\\
\sigma[5] - \sigma[4]  &= 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[1]$ 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[1]$ 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]$.
