c++ - 查询大小为 K 的所有连续子数组

Question

让我们在数组上定义一个操作 B[1:K]尺寸K即计算子数组中元素的数量 B[2:K]小于 B[1] .

现在我有一个数组 A[1:N]尺寸N我的目标是对所有大小为 K 的连续子数组执行上述操作.

例子

A = [4, 3, 6, 2, 1] and K = 3有3大小为 3 的连续子数组.

1. B = [4, 3, 6] count = 1 [(3 < 4)]
2. B = [3, 6, 2] count = 1 [(2 < 3)]
3. B = [6, 2, 1] count = 2 [(2 < 6), (1 < 6)]

蛮力方法的时间复杂度将为 O((N-K+1)*K)因为对大小为 K 的连续子数组执行上述操作是O(K) .

我可以高效地做到这一点，即 Nlog(M)如果我可以设计一个数据结构 具有以下属性

1. 插入 log(M)
2. 在 log(M) 中删除
3. 计算小于X的元素个数在 log(M)

我是C++用户，我认为没有任何数据结构可以满足所有提到的要求。还有其他改进方法吗？请帮忙。

Answer 1

您可能希望将 set 与对小于 k 的元素进行计数的附加操作一起使用。这可以实现为二叉搜索树(经典集合实现)，每个节点都有额外的统计信息(基本上是树中节点的大小)。

此处有更多详细信息:https://stackoverflow.com/a/15321444/1391392 这里有一些实现:https://sourceforge.net/projects/orderstatistics/

另一个看起来更直接的选项是使用跳过列表。 https://en.wikipedia.org/wiki/Skip_list