Help With Data Structure Identification — maintain sorted order, log(n) insertion, log(n) prefix sum

Revision en1, by insurgentes, 2023-07-23 07:52:34

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 nodet

Tags datastructure, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English insurgentes 2023-07-23 07:53:39 0 (published)
en2 English insurgentes 2023-07-23 07:53:21 5 (saved to drafts)
en1 English insurgentes 2023-07-23 07:52:34 776 Initial revision (published)