我正在尝试寻找解决这一挑战的方法：
给定 n，即一个由 1 填充的数组的大小。此数组上可以进行两种类型的操作：
- 增加（x，y，m）：将 m 添加到从位置 x 到 y（包括）的区间内的所有数组元素。1 <= x <= y <= n。
- 给出（x，y）：返回给定区间上的非减序列的最大长度。
例子：
输入：
n = 5：运营：
增加 1 2 3 (x = 1, y = 2, m = 3)
现在我们的数组是
[4, 4, 1, 1, 1]给出 2 4 (x = 2, y = 4)
最大长度为 2，因为最大非递减序列为 1, 1。
我寻找一个解决方案，其中每个操作都有 O(log(n)) 的时间复杂度。
我的方法
我注意到我们可以将此数组存储为零数组，其中每个元素表示它比前一个元素大多少。例如，[1, 4, 2, 5]我们有而不是[0, 3, -2, 3]。现在我们只需查看负数就可以轻松找到非递减序列。我曾尝试过这种方式并优化查找负数（例如通过使用集合或树），但在某些情况下，“给予”操作仍然具有 O(n) 复杂度，这不是我想要的。
我的算法是这样工作的：
请注意，如果我们使用一个零数组，我们可以只用两个步骤来改变它（当有增加操作时）：arr[x] += m 和 arr[y + 1] -= m（我假设 arr 是基于 1 的）。一开始我有一个新的空集。在增加操作期间，我执行上述两个步骤，然后：
如果“+= m”操作后 arr[x] 不小于 0，则从集合中删除 x。
如果“-= 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) 时间复杂度执行每个操作？