insurgentes's blog

Help With Data Structure Identification — maintain sorted order, log(n) insertion, log(n) prefix sum
By insurgentes, history, 9 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

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

segment tree + skip list

→ Reply
  • »
    »
    9 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
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 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
»
9 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
»
9 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