Assume a codeforces like platform where there are $n$ users and their ratings vary over time $[0, T]$.↵
Now given an interval $[l,r]$, we would like to find top k profiles which had highest delta in that interval.↵
↵
Is it possible to answer this query without iterating over $n$ interval sums? For example we can get $O(n\log(n)\log(T))$ by maintaing fenwick tree per user and sorting the list of interval sums.↵
↵
↵
Edit: Added requirement to avoid looping over $n$ users..↵
Now given an interval $[l,r]$, we would like to find top k profiles which had highest delta in that interval.↵
↵
Is it possible to answer this query without iterating over $n$ interval sums? For example we can get $O(n\log(n)\log(T))$ by maintaing fenwick tree per user and sorting the list of interval sums.↵
↵
↵
Edit: Added requirement to avoid looping over $n$ users..↵
