||I believe that we always need to compute the "k" described in the tutorial, which take time proportional to log(R-L),where [L,R] is the interval in which we do the RMQ. In worst case this could be log(N).
Thus i think the query time is O(log N). Am i wrong somewhere in my conclusion?
The bound described in the tutorial ignores this point.