Xellos's blog

Indexed set / array with wide functionality: treap
By Xellos, 8 years ago, In English 
const int *
int const *
int * const
int const * const
const int * function (const arg) const
return void(l = r = 0);

link to repo

VERSION 2.0 RELEASED! Now with 100% less memory leaks or MLE verdicts. Project moved from Github.

The following text is for version 1.0.

Based on the e-maxx implementation and other stuff I found online, I pieced together a powerful treap. It can be used as a set<>, array, segment tree or (within limits) all of them at once.

Consider a set<> represented as a sorted array of distinct elements. You can insert/remove elements just like in a set<>. You can also find the index of any element in this array, remove an element by index — or insert an element at an index, but that will probably break the sortedness and you can't use the operations which rely on it anymore (you can still insert/remove elements by index). As long as the array is sorted, you can query lower bound / upper bound of any element, given as a pair (element, index).

Next, you can reverse a range, add to a range and query range sums; this will work all the time, but range addition can and reversing will break the sortedness. You can implement your own queries (like min/max) or combined range updates (paint+add) like in a segment tree. Since we need lazy propagation, everything is immutable (you can work around it e.g. with erase/insert) and I decided not to bother with iterators.

I took special care with randomisation. It uses testlib random_t and if equal priorities are detected (at insert), they're all regenerated, but it shouldn't happen with reasonably small data — the priorities are 60-bit, which is far above the Birthday Paradox threshold for just about anything.

The DS is templated over some type T, which has to be comparable and support addition / subtraction / multiplication by int (like a vector space in math).

It supports the following operations, all online in (with N being the current number of elements, ofc):

function action returns
insert(element) inserts element into a set bool(was it inserted?)
insert_pos(index, element) inserts element at index void
erase(element) removes element from a set bool(was it removed?)
erase_pos(index) removes element at index void
get_index(element) finds the element's index, size() if non-existent int in [0..size()]
[index] finds the element at index T (not T&)
lower_bound(element) finds the lower_bound() of that element, with index pair<T,int>
upper_bound(element) the same with upper_bound() pair<T,int>
shift(left,right,element) add element to everything in the range [left,right] void
reverse(left,right) reverse the range [left,right] void
sum(left,right) find the sum of the range [left,right] T

Also, there's the usual empty(), size(), is_sorted() (returns true if the sortedness hasn't been broken yet) and srand(), which lets you choose your seed if you don't want the testlib default.

I compared it with STL set<> on a million insert/erase/lower_bound operations; the treapset is ~3-4 times slower (which makes sense, since the structure supports many more operations). I also tested it on a million insert_pos/get_index/shift/reverse/sum operations; it took ~4 seconds locally. It seems to work...

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

Comments Comments (6)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Some questions. What happens if there is no element at the position? (erase_pos). Similarly, what happens if you insert_pos at position 273472348, or something? Does it default to the size of the set?

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

Wow! This is so cool

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

I have got MLE here https://codeforces.me/contest/641/submission/189834153

all my code is 

int n;
map<int, treap<int>> mtp, mtm;
 
int main() {
  cin >> n;
 
  for (int i = 0; i < n; i++) {
    int a, t, x; cin >> a >> t >> x;
 
    if (a == 1) {
      mtp[x].insert(t);
    } else if (a == 2) {
      mtm[x].insert(t);
    } else {
      auto lbp = mtp[x].lower_bound(t);
      auto lbm = mtm[x].lower_bound(t);
      cout << lbp.second - lbm.second << endl;
    }
  }
}

Maybe not all bugs were fixed or am I doing something wrong?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Didn't check your code yet but not all bugs were fixed. I know about it from some older submission but didn't get to it.

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    205220953 Took me a while to get to it, but here it works. What happened: there are memory leaks I'm just fixing, but you ran out of memory for an unrelated reason.

    The real problem isn't a bug, it's by design — you have to choose RNG properly since the default became "allocate your own RNG" and that's a big object, which isn't a problem unless you're making potentially 200,000 of them like here. The non-default (but somewhat recommended) alternative is choosing your own RNG, in this case one for the whole program is sufficient:

    std::mt19937_64 default_rng;
map_of_treaps.insert({x, treap<int>(&default_rng)});

    I'll have to put proper info in the readme.

    → Reply