insurgentes's blog

Help With Data Structure Identification — maintain sorted order, log(n) insertion, log(n) prefix sum
By insurgentes, history, 16 months ago, In English

Hi all,

Can someone help me identify the right data structure that satisfies the constraints I outlined? - Should maintain sorted order when inserting (or allow for looking up the rank and inserting in that position) - Should have efficient insertion - Should have efficient prefix sums

I think what I need is a dynamic(?) segment tree that allows insertion at arbitrary points, but unsure how I would ensure it stays balanced. Any help would be appreciated.

Some things I tried to make work

  • gnu pbds as described in this post, seemed promising but does not allow me to add in the custom prefix sum logic at each node
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it -7 Vote: I do not like it

segment tree + skip list

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

    Are you talking about the offline method? I think OP is looking for a way to do it online.

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you don't want to use a treap you can use an avl tree where you also keep track of sums at each node. But this is much more complex to implement than a treap

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

    Yeah, I'm pretty new to treaps, but it seems like a simpler way to code up auto balancing binary trees (similar to Red-black/AVL). I might be totally off though, still trying to fully understand it.

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

      I dont really know how treap work but yeah, from what i've heard theyre much quicker to implement

      → Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

I think some $$$O(N*\sqrt{N*log(N)})$$$ is possible with SQRT decomposition. But I'd stick to the treap solution mentioned above

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

As mentioned, treap. In general, for any kind of BST, it's easy to recalculate sum over any affected node's subtree in $$$O(1)$$$, so you only need to figure out rebalancing. Treap deals with it using randomisation. Here I'll once again plug my treap implementation on which I had a blog post here — at the moment, it doesn't support multiset-style operations (you can use additional UIDs per key, it's just annoying), only set-style, but it supports all the stuff you want and more (add to segment while keeping sortedness!).

→ Reply