堆棧

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應該很容易實現。