Let's say we have array $A$ of $N$ integers, each of them in the range $[-1, 1]$. We define an array $B$ of $N+1$ integers, such that $$B_{N+1} = 0, \\B_i = A_i + A_{i+1} + A_{i+2} + \dots + A_{N}= A_i + B_{i+1}$$

So now we want to build data structure over the array $B$ such that it will be possible to perform two types of queries:

1.Update single element in array $A$, again in the range $[-1, 1]$, note that this update will also change array $B$.

2.For given $L$ and $R$ for each $i$ in $[L, R]$ find $\min B_i$.

I think that this can be solved with segment tree, but I'm trying to simplify the implementation, as it looks pretty complex.

  • $\begingroup$ When you say update an element in $A$, can this be both an increase or decrease or only one of the two? $\endgroup$ – orlp Jul 15 '18 at 11:25
  • $\begingroup$ The update operation is in this format: set the element at index $x$ in the array A to $y$. $y$ is going to be again in range $[-1, 1]$. $\endgroup$ – someone12321 Jul 15 '18 at 11:49

Your Answer

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

Browse other questions tagged or ask your own question.