Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?
This can be solved with split and join operations, both achievable in $\mathcal{O}(\log n)$ for Red-Black and AVL trees.
For Red-Black Trees this is doable either leveraging finger trees or via extending a regular Red-Black Tree as in Ron Wein's &quot;Efficient Implementation of Red-Black Trees with Split and Catenate Operations&quot; implemented in CGAL with criticisms mentioned in https://stackoverflow.com/questions/29029894/red-black-tree-split-concatenate-in-logn-time (Tarjan might have a better paper).
For AVL trees this is doable according to Ramzi Fadel and Kim Vagn Jakobsen's &quot;Data structures and algorithms in a two-level memory&quot;.
InsertInOrderSequentialBatch is expressable as a split followed by 2 joins. DeleteRange is 2 splits followed by 1 join.