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.