Problem: there are N players, each one starts with some initial score, therefore they appear sorted non-increasingly by their scores in a dynamic leaderboard. From time to time some player changes his score, and the leaderboard gets updated to reflect the player's new ranking (in case of ties, for simplicity let's assume ties are broken by comparing the players' unique IDs). At the same time, we need to answer queries of the form "What is the accumulated sum of the scores of all players with rank between L and R in the leaderboard?". Score updates and range sum queries are interleaved.

Does anybody know how to implement this efficiently? I know I can implement a dynamic ranking using STL policy based data structures, because I can query the current ranking of a player in O(log(N)), remove him in O(log(N)), insert him again with his new score in O(log(N)) and finally query his updated ranking in O(log(N)). However I don't know how to keep track of accumulated sums of ranked scores efficiently. Maybe some clever adaptation of segment tree or fenwick tree might be of help but I'm not sure how.

Any help is very appreciated.