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))$:
- Find node i (let say v) $\ O(\log(n))$
- Find node j (let say u) $\ O(\log(n))$
- Check if v.val + v.lsum - u.lsum == 0 $\ O(1)$
But if it comes to checking supergood condition, I don't see how.