轻松求非减序列在一定区间上的最大长度的数据结构

Question

我正在努力寻找应对这一挑战的解决方案：

给定n，它是用1填充的数组的大小。此数组上可能有两种类型的操作：

• Increase(x,y,m)：将位置x到y（含）区间内的所有数组元素添加m。 1 <= x <= y <= n.
• Give (x, y)：返回给定区间上非递减序列的最大长度。

示例：

输入：

n = 5

：

操作：

1. 增加 1 2 3（x = 1，y = 2，m = 3）

   现在我们的数组是

   [4, 4, 1, 1, 1]

2. 给出 2 4 (x = 2, y = 4)

   最大长度为 2，因为最大非递减序列为 1, 1。

我寻找一种解决方案，其中每个操作都有 O(log(n)) 时间复杂度。

我的方法

我注意到我们可以将此数组存储为一个由零组成的数组，其中每个元素代表它如何大于前一个元素。例如，我们有

[1, 4, 2, 5]

，而不是

[0, 3, -2, 3]

。现在我们只需查看负数就可以轻松找到非递减序列。我尝试这样做并优化查找负数（例如通过使用集合或树），但在某些情况下，操作“Give”仍然具有 O(n) 复杂度，这不是我想要的。

这是我的算法的工作原理：
请注意，如果我们将使用零数组，我们只需两步即可更改它（当有增加操作时）：arr[x] += m 和 arr[y + 1] -= m （我假设arr 是从 1 开始的）。一开始我有新的空集。在增加操作期间，我执行上述两个步骤，然后：

1. 如果“+= m”运算后的arr[x]不再小于0，则将x从集合中删除。

2. 如果“-= m”运算后的arr[y + 1]不再等于或大于0，则将y + 1添加到集合中。

完成所有增加操作后，我们将得到一组全负数。正如我上面所写，这些是非递减的间隔。例如，如果我们有

n = 6

和

set = {2, 6}

，我们就有 3 个非递减区间：(1, 1)、(2, 5)、(6, 6)。所以我们可以在 O(set.size()) 中进行 Give 操作，这是不好的。

如何以 O(logn) 时间复杂度执行每个操作？

Answer 1

这可以使用具有惰性传播的线段树来解决（或者，可以在二叉索引树中单独处理范围增加）。在每个节点中，存储节点表示的间隔上的增量总和以及三个最长的非递减子数组的长度：从左端点开始的子数组、在右端点结束的子数组以及整体最长的子数组节点区间内的任意位置。对于叶节点，所有三个长度均为 1，并且我们从每个节点的增量为 0 开始。

合并两个节点时，通过检查右侧元素是否存在，来考虑以左节点右端点结束的最长非递减子数组是否可以与以右节点左端点开始的最长非递减子数组组合应用增加后，前者的端点不大于后者左端点的元素（回想一下，增加操作的总和已经存储在每个节点中）。合并结果中从左端点开始的最长非递减子数组将与左节点具有相同的值，除非左节点中的最长非递减子数组覆盖了整个节点，在这种情况下它将是左右节点的组合结果（如果可能的话）。在右端点结束的最长非递减子数组的情况是对称的。

对于覆盖整个节点的递增操作，所有非递减子数组都保持非递减，因为所有元素都递增相同的量。只需要以惰性更新的形式跟踪这些（遍历线段树时遇到节点就将更新下推）。

查询和更新都可以在

O(log(n))

中完成。