0
$\begingroup$

I need to find a data structure that supports the following operations:

  • init(A): gets an array of size $n$ of different numbers and builds the data structure - should be $O(n)$.
  • max(i,j): gets two indexes $i<j$ and returns the maximum value between these two cells, that is, $A[i],A[i+1],\dots,A[j]$ - should be $O(\log n)$.

It should be a tree related data structure.

$\endgroup$
2
  • 1
    $\begingroup$ What are your thoughts? Have you tried solving this problem on your own? How far did you get? $\endgroup$ Apr 28, 2018 at 9:22
  • $\begingroup$ You may use Segment Trees! $\endgroup$
    – kiner_shah
    Apr 28, 2018 at 11:28

1 Answer 1

2
$\begingroup$

Assume for simplicity that $n$ is a power of 2. Construct a complete binary tree in which the vertices at depth $k$ correspond to subarrays of length $n/2^k$, and contain as auxiliary information the maximum element of the subarray.

This data structure can be initialized in $O(n)$, and it supports your type of range queries in $O(\log n)$. You can also update the data structure by modifying arbitrarily a single element of the array in $O(\log n)$.

Details left to you.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks, actually I came to this notion of using a tournament tree, but couldn't figure out how to find the max between 2 indexes that are not excactly signify start and end of a subarray, say 3-4. I mean, they do, but if a got it right I don't have a vertice that holds that max value exactly $\endgroup$
    – chendoy
    Apr 28, 2018 at 9:52
  • $\begingroup$ Right, there is still some work left to do. $\endgroup$ Apr 28, 2018 at 9:56
  • $\begingroup$ ok, I guess it has something to do with some comparisons between some vertices to determain this kind of max values $\endgroup$
    – chendoy
    Apr 28, 2018 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.