Here is the description of the data structure I am looking for:
Initial Original Data
Index | Frequency | 1 3 2 1 3 7 4 2 5 6
Now it should be kept Sort-ed by their frequency inside the data structure like this,
Index | Frequency | Cumulative Frequency | 2 1 1 4 2 3 1 3 6 5 6 12 3 7 19
Now, if I Insert a new entry item (index 6) with frequency of 2, the data structure should maintain it like this:
Index | Frequency | Cumulative Frequency | 2 1 1 4 2 3 ->6 2 5 1 3 8 5 6 14 3 7 21
Now, a frequency increase of 3 at Index 2 should Update the structure as following:
Index | Frequency | Cumulative Frequency | |2 1 1| 4 2 2 | 6 2 4 | 1 3 7 |-> 2 1+3 = 4 11 5 6 17 3 7 24
You can see above that the frequencies can repeat in many indices. (see index 4 and 6 above).
Now my Query to find the index that contains a cumulative frequency should be resulted in the following way
Query(cumulative frequency) | Result (Index at the data structure) 3 6 1 4 20 3 7 1
I have already explored Fenwick Tree (Binary Indexed Tree). It has a very efficient, O(log(n)), way to insert and update frequency at an index and to find the index for a specfic cumulative frequency. But I did not find a way to keep the Indexes sorted by their frequency.
Other structures like Treap, Red-Black tree can store the frequency in a sorted way but I could not find a way to search the index with the specific cumulative frequency using those data structures.
delete
+insert
; it's unlikely to get any better than that. $\endgroup$