c++ - 从一个数列中减去一个数后，剩下的数有多少是正数？

Answer 1

数据结构

对数据结构使用具有惰性传播的段树。

在每个节点存储中：

1. 所有子节点中正值的数量
2. 所有子节点的最小正值（即对于值为-1、3、5、-10 的子节点，最小的正值为3。我们忽略-1 和-10，因为它们不是正值。）
3. 从该节点减去待定值（初始化为 0）

更新

更新范围的过程将是：

1. 递归下降到段树中，直到找到一个完全被范围覆盖的节点
2. 修改节点的挂起值

询问

回答范围查询的过程将是：

1. 递归下降到段树中，直到找到一个完全被范围覆盖的节点
2. 如果节点的挂起值大于最小正值，则递归更新节点的属性

复杂

由于每个节点只能变为负数一次，我相信整个过程应该是 O(nlogn+qlogn) 其中 n 是序列的长度，q 是操作的数量。

例子

假设我们有数组 [1,5,-3,4]。

我们将有如下段节点：

[1,5,-3,4] min positive 1, pending change 0
[1,5] min positive 1, pending change 0
[-3,4] min positive 4, pending change 0

假设我们想用减 2 更新整个范围，我们将其更改为：

[1,5,-3,4] min positive 1, pending change 2.

现在，由于待处理的更改 >= 最小正数，我们需要通过递归地将更改推送到左孩子和右孩子来修复节点。

首先，左孩子将变为：

[1,5] min positive 1, pending change 2

然后我们将再次展开该节点并应用更新成为

[-1,3] min positive 3, pending change 0

接下来我们会找到正确的孩子，它会变成

[-3,4] min positive 4, pending change 2

但由于未决更改<最小正数，因此不需要进一步递归。

最后递归将再次到达顶层节点。我们使用左右孩子的属性来计算现在最小正数为 2（从最小为 4 和待定 2 的右孩子给出 4-2=2 的结果），我们可以将待定更改重置为 0因为它已经应用到孩子身上了。

Answer 2

一种易于编码的数据结构称为段树。
一种更快但更难编码的数据结构称为二进制索引树。