I am interested in knowing if there is a data structure that can offer better than O(log n) average complexity and offers the following 2 operations:

Increment x-> V[x] = 1 (all elements are initially 0) Query (1->y) all query are 1 based...

I know I will have O(n) increases and O(n) queries and want better than O(n log n) total time...