determinism's blog

A Data Structure Problem
By determinism, 10 years ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the range of the values?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    There can be 4e5 queries, and val is between 0 and 1e6 (inclusive).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Cartesian tree support all this operations.

You can read about it in this post

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

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)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    You don't have to compress vals in this task.

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

You can solve it by using self-expanding segment trees in O(M*log(maxVal)) time and O(M*log(maxVal)) memory. my implementation

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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.me/blog/entry/11080

→ Reply