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 '18 at 9:22
  • $\begingroup$ You may use Segment Trees! $\endgroup$
    – kiner_shah
    Apr 28 '18 at 11:28
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$
    – user112112
    Apr 28 '18 at 9:52
  • $\begingroup$ Right, there is still some work left to do. $\endgroup$ Apr 28 '18 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$
    – user112112
    Apr 28 '18 at 9:59

Your Answer

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

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