algorithm - 更新和查询数组 >= X 中的所有元素，其中 X 快速变化

Question

正式地，我们得到一个带有一些初始值的数组。然后我们有 3 种类型的查询:-

1. 点更新:在给定位置增加 1
2. Range Queries : To count number of elements>=x 其中x作为输入
3. 范围更新:将所有元素递减 1>=x，其中 x 作为输入给出。

N=10⁵ , Q=10⁵ (数组中元素的数量，查询的数量)

我尝试使用线段树执行此操作，但操作 2,3 可能比 O(n) 更糟糕，即使我们不知道要准确更新哪个“范围”，所以我们最终可能会遍历整个线段树。

注意:我想明确一点，如果我们需要在对数最坏情况下执行所有 3 个操作，即 O(log n)，因为只有这样我们才能快速执行此操作，线性方法不会' t 工作为 Q=10^5 n N=10^5 ，所以最坏的情况可能是 O(n^2) ，即 10^10 操作，这显然是不可行的。

Answer 1

鉴于您正在谈论 10⁵ 个项目，并且没有提到需要添加或删除项目，在我看来，明显的数据结构将是一个简单的排序向量。

操作复杂度:

1. 点更新:O(1) + O(m)(其中 m 是等于更新前值的后续元素的数量)。
2. 范围查询:O(log n) + O(m)(其中 n 是范围的开始，m 是范围内的元素)。
3. 范围更新(与范围查询相同)。

要确定“快速”对您意味着什么有点困难，但理论上最快的 1 可能是 O(1)，因此我们已经处于最优的某个常数因子内。

对于 2 和 3，即使我们能够以恒定的复杂度进行查找，我们也几乎只能使用 O(m) 进行更新。由于 Log₂100000 = ~16.6，大部分时间 O(m) 项将占主导地位(即，更新部分将涉及与搜索一样多的操作，除非给定的 x 是集合中最后 17 个项目之一。

我怀疑这么小的集合有任何意义，但如果您可能必须处理更大的集合并且集合中的项目合理地可预测地分布，则可能值得考虑进行插值搜索而不是二进制搜索。对于可预测的分布，这会将预期的比较次数减少到大约 O(log log n)。在这种情况下，大约为 4(但通常具有更高的常数因子)。这可能是 10⁵ 项的胜利，但也可能不是。如果您可能必须处理一组(比方说)10⁸ 项或更多项，则更有可能取得重大胜利。