3
$\begingroup$

Lets consider sequences whose elements are $-1,0,1$.
Subsequence $A[i...j]$ is $good$ if sum of its elements $=0$.
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is $good$.

Subsequence $A[i...j]$ is $supergood$ if it is good and every its prefix-sum is $>= 0$
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is not $supergood$ but $1,0,-1$ is $supergood$.

Now I want to have dynamic data structure which allows me efficiently do these operations:

  • Insert(S,x,i) - inserts $x$ into $S$ on $i$'th position
  • Remove(S,i) - Remove $i$'th element
  • isSuperGood(S, i, j) - checks if subsequence $i$, $j$ is supergood

The solution could be AVL tree with sum of elements in left and right subtree. It is easy for update and allows us to check if subsequence is good in $O(\log(n))$:

  1. Find node i (let say v) $\ O(\log(n))$
  2. Find node j (let say u) $\ O(\log(n))$
  3. Check if v.val + v.lsum - u.lsum == 0 $\ O(1)$

But if it comes to checking supergood condition, I don't see how.

$\endgroup$
4
$\begingroup$

Augment the tree to store, for each subtree, the minimum of the prefix sums of the sequence of elements in that subtree. Then you can check the supergood condition in $O(\log n)$ time. It's your exercise, so I'll let you work out the details.

Hint #1: every prefix can be decomposed into a union of $O(\log n)$ subtrees.

Hint #2: the minimum of the prefix-sum of elements $[x_1,\dots,x_k]$ is the smaller of (a) the minimum of the prefix-sum of elements $[x_1,\dots,x_j]$, (b), the sum of elements $[x_1,\dots,x_j]$ plus the minimum of prefix-sum of elements $[x_{j+1},\dots,x_k]$. Now let $[x_1,\dots,x_j]$ denote the elements in the left subtree of a node, and $[x_{j+1},\dots,x_k]$ the element in the node and the elements in the right subtree, and this gives you a way to recompute the augmented values in a node given the augmented values in its two children.


In general, the typical strategy with augmentation is that you want to choose augmented values so that (1) you can update or recompute the augmented values in a node efficiently (typically, in $O(1)$ time), given the augmented values in its two children, and (2) you can answer a query efficiently (typically, in $O(\log n)$ time), using the augmented values. Often we handle (2) by taking advantage of the fact that every interval of consecutive values can be decomposed into a disjoint union of $O(\log n)$ subtrees.

$\endgroup$
  • $\begingroup$ Great, thanks. I got how can it be updated during insertion, deletion and how to answer supergood(i,j). Now I wonder how insert node at specific position? Let say that I want to inser $-1$ and $k$ position. I can in $log$ time find that position. But if it is not leaf I have to do something with element existing there. Is there any pattern here? $\endgroup$ – Tester1998 Jan 4 at 10:07
  • $\begingroup$ @Tester1998, use Hint #2 (see updated answer). $\endgroup$ – D.W. Jan 4 at 18:20
  • $\begingroup$ Got that, thanks. $\endgroup$ – Tester1998 Jan 6 at 18:32

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.