Hello , i want to know how to do a binary search for something ( like lowerbound for a value ) on a binary indexeded tree in (log ( n ) ) . On a segment tree it can be done in Log ( N ) but on binary indexed tree the naive binary search is LOG^2 ( n ) . So does anyone know how to make it in Log(n) ? thanks in advance .

http://www.spoj.com/problems/FREQUENT/ . I solved this question using segment tree but i was wondering if it can be solved with MO's algorithm . Does anyone have an idea of how to apply MO's algorithm on this and keep track of the most frequent value along with it . Thanks in Advance.