Range Max Query

#1

Can anyone tell me if it’s optimal to implement range max query using square root decomposition , because in that case each update would take O(sqrt(n)). In the square root decomposition section too only range sum query is described in which update is O(1) , so square root decomp. method works in that case. Or we should just use segment trees for such cases ?

#2

@pswaldia1,
Yes you can use Sqrt Decomposition,
Complexity Analysis,

  • Point Update -> O(sqrt(n))
  • Range Update -> O(n)
  • Range Query -> O(sqrt(n))
#3

Abhijeet… correct me if i am wrong but in this case point update would mean computing the max for a complete segment which will take O(sqrt(n)). Unlike in Range Sum Query in which we were able to compute new sum after update in O(1)

#4

So point update will also take O(sqrtn) to compute new max for a segment. which might not pass the constraints.

#5

@pswaldia1,
Yes sorry for the mistake, you are correct Point update will take O(Sqrt(n)) but no it will not cause TLE as still complexity of code is O(q.sqrt(n)). q=no. of queries, n = no. of elements in array.

1 Like
#6

Thanks for the reply.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

Page not found error on above link.