I need a data structure that supports 4 operations:
- ADD( val ) : Adds val (which is a number) to data structure
- REMOVE( val ) : Removes val from data structure
- SUM( val ) : Returns sum of all elements greater than val
- NUM( val ) : Returns number of all elements greater than val
Operations should be better than O(n) in terms of time complexity. Do you have any ideas?
What is the range of the values?
There can be 4e5 queries, and val is between 0 and 1e6 (inclusive).
If numbers are smaller than 10^6, you can do a simple segment or fenwick tree on the value range. If you add number x, then just add +x the xth element in your tree, and for remove do -x for the xth number. For sum queries just get the sum on the rage [x+1,10^6]. Similar for number of element greater than x.
Cartesian tree support all this operations.
You can read about it in this post
Here's solution with segment tree.
First, compress all 'val's from all queries. Then you will have a map<int, int> new_value. new_value[x] means the number x became new_value[x] after compressing.
Now you have all M queries, val from each query is less or equal to M. Ok, make a segment tree of [1..M] elements, which have sum and cnt in each node. Then, you can easily answer each query updating the compressed position.
ADD val => update position new_value[val] in segment tree (sum[pos] += val, cnt[pos]++)
REMOVE val => sum[pos] -= val, cnt[pos]--
SUM val => get_sum(new_value[val]+1...M)
NUM val => get_cnt_sum(new_value[val]+1...M)
You don't have to compress vals in this task.
You can solve it by using self-expanding segment trees in O(M*log(maxVal)) time and O(M*log(maxVal)) memory. my implementation
AVL/Red Black trees do the trick. You need to maintain at each node the sum of values in left subtree and right subtree.
You can use STL policy based data structures, refer http://codeforces.com/blog/entry/11080