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
segment tree + skip list
Are you talking about the offline method? I think OP is looking for a way to do it online.
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
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.
I dont really know how treap work but yeah, from what i've heard theyre much quicker to implement
I think some $$$O(N*\sqrt{N*log(N)})$$$ is possible with SQRT decomposition. But I'd stick to the treap solution mentioned above
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!).