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.