Black_hat123's blog

Help in a range query question
By Black_hat123, history, 5 years ago, In English

Hello, can any one please tell how to solve this question

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Basically the problem is, given array $$$A$$$ of length $$$n$$$, queries of the form

  1. find $$$x$$$ : find leftmost index with $$$A_i >= x$$$

  2. upd $$$i$$$ $$$y$$$ : increase $$$A_i$$$ by $$$y$$$

So we need to use a segment tree to maintain RMQ of $$$A$$$. Updates are standard. When a query comes, we first check for maximum in the interval $$$[1,n]$$$. If it's $$$< x$$$ then the ans is $$$0$$$. Otherwise check if max in $$$[1,n/2] >= x$$$. In that case we move left, otherwise we go right and query.

Complexity : $$$O(n lg n)$$$

→ Reply