algorithm - 快速返回订单统计的算法叫什么？

Question

我知道我想让算法做什么，但我想看看是否已经用 python 为我实现了，我需要知道算法的名称。

我想在容器中插入一组 [0,65535] 范围内的值。然后我想向容器询问任意订单统计信息。插入和查询都应该是对数的。

Answer 1

执行此操作的标准方法是使用扩充二叉搜索树。本质上，除了保留存储在树中的键集外，您还保留存储在每个子树中的节点数。这使您可以高效地使用计算机进行订单统计。

由于您处理的是有界整数，因此您可以只保留一个二叉搜索树，其中存储了 65536 个值，并计算每个子树中存储的元素数量。这会产生 O(lg 65536) 而不是 O(lg n) 的运行时间。