# Data structure with init $O(n)$ and interval max $O(\log n)$

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.

• What are your thoughts? Have you tried solving this problem on your own? How far did you get? Apr 28 '18 at 9:22
• You may use Segment Trees! Apr 28 '18 at 11:28

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)$.