堆栈

Question

执行3个行动，我给出一个空栈，我需要支持三种操作：

PUSH x : Push element x onto the stack 
POP : Pop the top element 
INC L R x : Increment the L to R elements by x 

每个查询我要告诉阵列的顶级元素之后。如果他们可以是10^6查询，怎么做这个问题。

我们无法一次又一次更新所有元素。所以请提供有效的解决方案。

Answer 1

将会有比弹出操作更多的推动，否则堆栈将最终为空。寻找最后一个没有相应弹出窗口的按钮，这是最后会在堆栈顶部的元素。现在简单地为每个适当的公司操作增加这个元素。

复杂度的这种方法：

O（2n）后计算

O（查询）存储器

N =所有的操作的总数查询

Answer 2

我们可以用一个segment tree那在O(log n)支持您所需的操作：

1. 个增量在给定的范围内

所有元素对于您的段树的间隔相关联的每个节点包含在给定范围内，增加一个计数器num_increments吧：这个计数器会告诉你多少次，元素在这个范围内都增加了。只有为最顶级的节点做这件事，一旦你做完这些，不要递归地回到他们的孩子身上。

查询给定索引

这个问题的答案是v[index] + number_of_increments处的值。您可以通过在分段树中查找与索引关联的节点并在走向它时跟踪其父节点的值来找到增量的数量。

有一对夫妇的事情要考虑，这取决于您的具体问题：

1. 对于给定的L, R，也许设定R = min(R, stack.Size)，因为它是没有意义的堆栈增加的元素还没有。或者它可以解决你的问题，我不知道。如果它确实对你的问题有意义，它会让事情变得更容易，并使我的第二点失效;

2. 当你从堆栈中弹出一个元素时会发生什么？此方法仍然会将其位置标记为递增，因此如果将其后移一位，则会考虑将其递增1.考虑如何还可以支持给定索引的递减（与查询操作类似）。

增量方向由x代替1应该很容易实现。