我有长度为N的号码序列。 我会做这个数字序列q操作。
在每次操作中我将给出三个整数P，Q，V与P≤Q≤N和将从每iᵗʰ整数，其中P≤I≤Q减去诉
每次手术后，我将得到另外两个整数X，Y与X≤ÿ≤ñ。 我必须回答多少Xᵗʰ和Yᵗʰ之间的整数（含）的整数是积极的。
Q将围绕10 5。 我会做所有的操作和周围1/2秒回答相应的问题。
我应该使用什么算法/数据结构？ 并且该过程将是什么？
注：我有段乔木或二进制索引树一个体面的知识。 如果您的解决方案涉及到这些数据结构，这将是巨大的。
Answer 1:
数据结构
使用线段树与用于数据结构懒惰传播。
在每个节点存储：
- 正值的所有子节点数目
- 所有子节点的最小正值（即与值-1,3,5-孩子，-10最小正值3.我们忽略-1，-10，因为他们不是积极的。）
- 待定值减去形成该节点（初始化为0）
更新
用于更新的范围内将是该过程：
- 递归下降到段树，直到找到那个完全被覆盖范围内的节点
- 修改待定值的节点
询问
回答查询的范围将是过程：
- 递归下降到段树，直到找到那个完全被覆盖范围内的节点
- 递归地更新节点的属性，如果该节点的待定值大于最小正值更大
复杂
由于每个节点只能成为负一次，相信这整个过程应该是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:
一个易于代码数据结构被称为段树。
快，但很难对代码数据结构被称为二进制索引树。
文章来源: After subtracting a number from a sequence, how many of remaining numbers are positive? [closed]
