algorithm - 数组的范围更新和查询

Question

我对包含 n 个元素的数组 A 进行了更新和查询。
我有两种类型的查询:
type 1 (Update) : 给定x，递减数组A中所有大于等于x的元素的值。
类型 2(查询):给定 (l, r, x)，找到数组 A 中第 x 个最小的元素，其值介于 l 和 r(包括两者)之间。

除了蛮力之外，我想不出更好的解决方案，这可能与 O(q*n) 一样昂贵。有什么最优解吗？数组 A 的元素可以大到 10^18。

Answer 1

我正在考虑的数据结构是自平衡二叉树的增强变体，例如 AA 树。除了普通成员之外，每个节点还存储隐式应用于其后代的减量计数。与其改变数字本身，不如从每个祖先节点中减去递减计数来查看节点的最终值。每个节点还维护其后代的计数。

更新包括对树的绑定(bind)搜索(复杂度 O(log n))，以及递增 O(log n) 节点的递减计数。在某些情况下，您还必须将边界下方的元素移动到该树中(因为它们不再小于所有元素，这要归功于递减)，这也是 O(log n)。 (请注意，最后一点需要一些棘手的后代更新，但我认为它不会破坏整体界限。)

“查询”操作很简单；二进制搜索找到 l(r 与操作无关，AFAICT)然后使用后代计数加速找到该范围内的第 k 个最小值到 O(log k)。

所以这两个操作的时间都是O(log n)，总时间是O(q*log n)，假设你不计算 O(n*log n) 构建初始树的时间。