Maintaining an array supporting sum requests

Question

We have to maintain an array $a_1,\ldots,a_n$ supporting the following operations:

1. Assign $a_i = x$
2. Given $\ell,r$, return $\sum_{i=\ell}^r a_i$
3. Given $\ell,r$, return $\sum_{i=\ell}^r \sum_{j=\ell}^r a_i a_j$
4. Given $\ell,r$, return $\sum_{i=\ell}^r \sum_{j=\ell}^r \sum_{k=\ell}^r a_i a_j a_k$

After $O(n)$ initialization, these operations should run in amortized $O(\log n)$ time.

Answer 1

Suppose for simplicity that $n = 2^N$ (otherwise, extend the array by zeroes). Maintain the following values: $$ a_1, \ldots, a_n \\ a_1 + a_2, a_3 + a_4, \ldots, a_{n-1} + a_n \\ a_1 + \cdots + a_4, a_5 + \cdots + a_8, \ldots, a_{n-3} + \cdots + a_n \\ a_1 + \cdots + a_8, a_9 + \cdots + a_{16}, \ldots, a_{n-7} + \cdots + a_n \\ \cdots \\ a_1 + \cdots + a_{n/2}, a_{n/2+1} + \cdots + a_n \\ a_1 + \cdots + a_n $$ By computing each line from the preceding one, you can compute all of these sums in $O(n)$.

Operation 1 can be implemented in $O(\log n)$ since each element is only involved in $\log n$ sums.

Operation 2 can be implemented in $O(\log n)$ since the sum can be broken into $O(\log n)$ sums of the type above.

Operation 3 and Operation 4 easily reduce to Operation 2 (exercise).

Details left to you.