c++ - Deleting element from Binary Index Tree -

i have binary index tree(bit) has stored distinct sorted values. eg. query(1) returns 1, query(2) returns 2 , on.

i want find nth maximum element in bit. element should not repeated next time. eg. 4th maximum 4. next time 4th maximum 5, after 4th maximum 6.

one way thought nth maximum , delete element bit or left shift elements right element 1, not repeated next time. not able find out how delete element or shift elements of bit.

can tell how if possible?

the basic bit data structure looks this:

value 1|2|3|4|5|6    f     1|0|2|1|1|3    c     1|1|3|4|5|8    tree  1|1|2|4|1|4 

where:

f[i] - frequency of value index i, = 1 .. maxval
c[i] - cumulative frequency index (f[1] + f[2] + ... + f[i])
tree[i] - sum of frequencies stored in bit index

(the above directly article).

looking @ above data structure, can see not possible delete in o(log n) time. imagine want delete first element tree. in order this, need update f[0], c[0], , tree[0], reflect element no longer exists in tree. unfortunately, need iterate through rest of c structure since represents cumulative sum. after setting c[0] 0, c[1] no longer accurate, , must updated, , c[2] no longer accurate... through c[n-1].

this o(n) operation in worst case, worst case being deletion of first element in tree.

i think smarter choice use different data structure. bits , other binary trees finding , adding elements efficiently, not @ removing elements. recommend using priority queue instead. priority queues (see this wikipedia article), use min-heap underlying data structure, , guarantee o(log n) removal.