范围最小查询、动态数组、区间树、treap
Range minimum query, dynamic array, interval tree, treap
我需要一个在 Python 中具有某种数据结构的算法，在给出两个新元素 e1、e2 时的每一步：
- 找到第一个和第二个给定元素的插入位置（保持顺序）。
- 求两个插入位置之间的区间内元素的最大值
- 在先前找到的第二个给定元素的插入位置插入，第二个给定元素与区间中找到的最大值加上一个常数配对。除非第二个给定元素已经存在，在这种情况下，我们只需要在新值更大时更新它的值。
并且这一步必须在对数时间内完成，因为当这一步重复N次时，整体最坏情况的时间复杂度不会远离O(NlogN)。
--
例如：
my_list = [(2,1), (4,3), (5,7), (9,1)]
如我们所见，元素 2 与其赋值 1 配对，元素 4 与值 3 配对，5 与值 7 配对，9 与值 1 配对。并且 my_list 是有序的按对的第一个元素。
现在，给定两个元素，e1 = 3，e2 = 6。
(e1, ) == (3, )在my_list中的插入位置为index 1，(6, )的插入位置为index 3。
在my_list的索引1和3之间的元素中找到的最大值为7，因为(4,3),(5,7)的最大值为7.
假设要加的常量为 1，我们有：找到的最大值 + 常量 == 7 + 1 == 8。
我们有 e2 == 6，所以要插入的对是 (6, 8) 在索引 3.
并且在此步骤结束时 my_list 必须是：[(2,1), (4,3), (5,7), (6,8), (9,1) ]
--
这个 非常相似，但与我关于插入元素的索引的问题不同。在那个问题中，元素被添加到末尾（附加），在我的例子中，插入必须以保留元素顺序的方式完成，以便可以在对数时间内找到下一个任意间隔的开始和结束.这就是为什么我认为，除了使用范围最小查询外，我还需要使用一些高级数据结构，如间隔树或 treap。
对于这类工作，我通常使用增广B+树。看这里什么是 B+ 树：https://en.wikipedia.org/wiki/B%2B_tree
从 B+ 树开始，我将扩充所有内部节点，以便与每个指向子节点的指针一起存储与以该子节点为根的子树中所有键关联的最大值。
这些额外的信息使得计算 O(log N) 中任何区间的最大值变得容易，并且在不更改 O(log N) 的情况下插入、删除和修改树中的项目时易于维护) 这些操作的复杂性。
对于内存中的 B+ 树，每个节点最多 8 个左右的键通常是高性能的。
我需要一个在 Python 中具有某种数据结构的算法，在给出两个新元素 e1、e2 时的每一步：
- 找到第一个和第二个给定元素的插入位置（保持顺序）。
- 求两个插入位置之间的区间内元素的最大值
- 在先前找到的第二个给定元素的插入位置插入，第二个给定元素与区间中找到的最大值加上一个常数配对。除非第二个给定元素已经存在，在这种情况下，我们只需要在新值更大时更新它的值。
并且这一步必须在对数时间内完成，因为当这一步重复N次时，整体最坏情况的时间复杂度不会远离O(NlogN)。
-- 例如： my_list = [(2,1), (4,3), (5,7), (9,1)]
如我们所见，元素 2 与其赋值 1 配对，元素 4 与值 3 配对，5 与值 7 配对，9 与值 1 配对。并且 my_list 是有序的按对的第一个元素。
现在，给定两个元素，e1 = 3，e2 = 6。
(e1, ) == (3, )在my_list中的插入位置为index 1，(6, )的插入位置为index 3。
在my_list的索引1和3之间的元素中找到的最大值为7，因为(4,3),(5,7)的最大值为7.
假设要加的常量为 1，我们有：找到的最大值 + 常量 == 7 + 1 == 8。 我们有 e2 == 6，所以要插入的对是 (6, 8) 在索引 3.
并且在此步骤结束时 my_list 必须是：[(2,1), (4,3), (5,7), (6,8), (9,1) ]
--
这个
对于这类工作，我通常使用增广B+树。看这里什么是 B+ 树：https://en.wikipedia.org/wiki/B%2B_tree
从 B+ 树开始，我将扩充所有内部节点，以便与每个指向子节点的指针一起存储与以该子节点为根的子树中所有键关联的最大值。
这些额外的信息使得计算 O(log N) 中任何区间的最大值变得容易，并且在不更改 O(log N) 的情况下插入、删除和修改树中的项目时易于维护) 这些操作的复杂性。
对于内存中的 B+ 树，每个节点最多 8 个左右的键通常是高性能的。