1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can implement operations 3 and 4 using operation 2. $\endgroup$ – Yuval Filmus Apr 21 at 17:15
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Maxim Apr 21 at 21:22
  • 1
    $\begingroup$ Putting constants inside big O is meaningless. In addition, you only have to do operation 2 once. $\endgroup$ – Yuval Filmus Apr 21 at 21:23
  • $\begingroup$ 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? $\endgroup$ – Maxim Apr 21 at 21:33
  • $\begingroup$ Both sums are equal. $\endgroup$ – Yuval Filmus Apr 21 at 21:34
  • $\begingroup$ How to solve a my problem if operation 3 is: sum ai * aj (i < j from l to r)? $\endgroup$ – Maxim Apr 21 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.