algorithm - 如何创建具有此类属性的数据结构

Question

我必须设计一个数据结构，使我有一个大小为 N 的数组 A，即 A[1],A[1],A[2],...A[n] .我必须处理两种类型的查询(总共有 M 个查询):

1. 在数组A中从i到j的范围内加1
2. 在数组A中找到第K小的元素

给定1<=N,M<=200000.

首先，我想到了通过对每个桶进行排序来进行平方根分解，但无法更新属于不同桶的部分范围。你能建议如何去做吗？

我想要一些 O(N*Log(N))或 O(N*SQRT(N))复杂性。

Answer 1

这看起来像是一个相当典型的竞争性编程问题。我想我有一个解决方案，虽然它有点难看 - 也许你可以改进它。

我们将在解决方案的核心使用平方根分解(如果您不熟悉此方法，请参阅 link)。对于每个 block ，我们将保留:原样的元素值(我们将其命名为 A)，整个 block 的添加数(一个整数，我们将其命名为 extra ) 和 IND - 按值排序的 block 索引数组(例如，如果 block 元素为 [4, 2, 5]，则索引数组将为 [1, 0, 2])。现在让我们来看看这如何让我们解决问题以及复杂性是什么。

初始化

对于每个 sqrt(N) block ，我们必须对其进行排序(sqrt(N) * log(sqrt(N)) 每个 block )，以获得初始索引数组，导致 sqrt(N) * sqrt(N) * log(sqrt(N)) = N * log(N) 初始化复杂度。

将 1 添加到范围 (l, r)

就像进行常规的 sqrt 分解更新一样进行。对于完全在范围内的每个 block ，我们将增加 extra 计数器。一个重要的观察是元素的相对顺序没有改变，所以我们在这里的工作已经完成。对于部分在更新范围内的 block ，我们执行以下操作:通过将适当的元素递增 1 来更新 A，通过排序重新生成 IND 数组。请注意，最多有两个部分更新 block 。 O(1) 中“完整” block 更新的总复杂度，其中有 sqrt(N)。部分更新是 sqrt(N) * log(sqrt(N)) = sqrt(N) * log(N)，总更新复杂度为 sqrt(N) * log(N )。有 M 个查询，所以在最坏的情况下，这些更新将贡献 M * sqrt(N) * log(N)。

找到第K小的元素

让我们弄清楚如何找到数组中小于某个值 L 的元素数。为此，对于每个 block ，我们将对 IND 数组进行二进制搜索。当我们从该数组中获得一些索引 idx 时，要使用的实际值是 A[idx] + extra，其中 A 和 extra 来自那个 block 。此过程允许我们获取每个 block 内大于 L 的元素数。之后，我们只需对每个 block 的结果求和。要处理一个 block ，我们必须花费 log(sqrt(N)) = log(N) 进行二分查找，并且有 sqrt(N) 个 block ，导致 sqrt(N) * log(N) 复杂度。

为了得到第 K 个最小的元素，我们将对可能的答案进行另一个二进制搜索(竞争编程中的常用技术)，我们将在最小和最大可能答案(例如最小元素和最大元素)之间进行二进制搜索加上 M)。我们将此范围表示为 C。在每一步中，我们都会检查有多少元素小于我们当前的猜测，当我们找到第 K 个最小的元素时，我们就会得到答案。如果您需要对此步骤进行更多详细说明，请告诉我。

最终复杂度变为log(C) * sqrt(N) * log(N)，可以有M个查询，使得M * log(C) * sqrt( N) * 日志(N)。如果初始数组全为零或值在 0 到 M 范围内，这将是 M * log(M) * sqrt(N) * log(N )。或者您可以选择将 C 视为常量(这不太正确)。

我很确定其中一个 log 可以被削掉，但这留给读者作为练习:)