Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time? Given a self-balancing binary search tree of size $n$, I want to perform the following operations:

InsertInOrderSequentialBatch an ordered sequence of $k$ values (specialized $k \in \{2, 3, 4\}$ or generalized $k \in N $) which are guaranteed to be sequential in an in-order tree traversal immediately after insertion.

For example, insert $[310, 320, 330, 340]$ into a balanced tree containing $[100, 200, 500]$.

Future insertions might still be between the inserted nodes' values.



DeleteRange all of $k$ nodes (likewise specialized or generalized) between 2 values in the BST.


For both operations, I want the tree to remain balanced.
With a Red-Black or AVL tree, I can achieve both operations through a sequence of $k$ insertions/deletions in $\mathcal{O}(k \log n)$, but wonder if a data structure (e.g. AVL/RB tree variant) could achieve $\mathcal{O}(\log n + k \log k)$ time for a real-world performance gain (e.g. traverse tree for insertion point, insert balanced tree into insertion point, perform one auto-balance pass)?
My needs are less theoretical and more in terms of wall-time &amp; memory pressure for an implementation of Fortune's Algorithm - an algorithm with high constant-time multipliers is unfortunately not useful. My insertion sequence is biased &amp; frequently multimodal (modes not known prior) with long streaks of insertions/deletions within modes. My tree size is anywhere from 100 to 3000 nodes.
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.