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

Правка en3, от insurgentes, 2023-07-23 07:53:39

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
Теги datastructure, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский insurgentes 2023-07-23 07:53:39 0 (published)
en2 Английский insurgentes 2023-07-23 07:53:21 5 (saved to drafts)
en1 Английский insurgentes 2023-07-23 07:52:34 776 Initial revision (published)