Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency
This can be easily handled using a standard balanced tree data structure, augmented with a Fenwick tree and a hashmap:


Store the items in a binary tree.  Each leaf stores information about a single item.  The leaves should be stored in increasing frequency, i.e., sorted by frequency, from least frequent to most frequent.
To help compute the cumulative frequency, augment the binary tree to store some additional information in each node.  In each node, store the sum of the frequencies of all of the items underneath it (i.e., of all of the leaves under that node).  These values can be easily updated as the tree changes.  This is basically the idea behind Fenwick trees for computing prefix sums.
Also, add a hashmap that maps from the value (what you call "index") to the associated leaf where that index is found in the binary tree.


Now you can support all of the operations you mentioned efficiently.  If you use a standard balanced binary tree data structure, the running time for all operations is $O(\log n)$:


Sort: All of the items are already stored in sorted order, sorted by increasing frequency, so this happens automatically.
Insert: You can insert a new item into the tree in $O(\log n)$ time.
Update: You can increase the frequency of a particular item by deleting it from the tree, increasing its frequency, and inserting it into the new location.  In a balanced binary tree, this takes $O(\log n)$ time, since deletion can be done in $O(\log n)$ time, as can insertion.
Query: You can now find the first index $i$ where the sum of the frequencies of the first $i$ leaves is at least $t$, by using binary search.  Note that you can efficiently compute prefix sums of the frequencies by using the extra values stored in each node of the tree.  Therefore, binary search suffices, and can be done in $O(\log n)$ time.


There are many balanced binary tree data structures, including red-black trees, AVL trees, 2-3 trees, etc.  They all have the property that standard operations are guaranteed to take at most $O(\log n)$ time.  You can use any of them for your purposes.