# Maintaining an array supporting sum requests

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.

• You can implement operations 3 and 4 using operation 2. – Yuval Filmus Apr 21 '20 at 17:15

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.

• Did I undestand you correctly, that 3 Operation should be like this: we do that we did in Operation 2 two times. And asymptotic is O(2log(n)). Am I thinking right? – Maxim Apr 21 '20 at 21:22
• Putting constants inside big O is meaningless. In addition, you only have to do operation 2 once. – Yuval Filmus Apr 21 '20 at 21:23
• Why I do this operation once? First time to count first sum, second time to count second sum. How I can do operation 3, only once use operation 2? – Maxim Apr 21 '20 at 21:33
• Both sums are equal. – Yuval Filmus Apr 21 '20 at 21:34
• How to solve a my problem if operation 3 is: sum ai * aj (i < j from l to r)? – Maxim Apr 21 '20 at 22:20