algorithm - 段树或 BIT 树上的插入和删除？

Question

我很难解决 Leetcode 307 Range Sum Query - Mutable and Leetcode 528: Random Pick with Index 的变体，以便设计一个数据结构，以便我可以添加元素，并且每个元素都将具有权重和基于 pop 元素与重量成正比。我正在考虑添加和弹出操作的最佳复杂度为 o(log n )，其中 n 是现有数据大小。但是，我可以找到一个好的算法/数据结构来解决它。

Answer 1

Splay Tree（或其他自平衡 BST）将支持在任意位置插入/删除、范围和查询，以及摊销 O(lgn) 中的 lower_bound/upper_bound。