使用兩個fenwick樹（二叉索引樹）的RMQ

Question

基於此paper，我發現在O(lg N)中使用兩個BIT來完成RMQ是相當出色的，因爲它比段樹更容易編碼，而且該文章聲稱它性能也比其他數據結構好。

我明白如何構建樹以及如何執行查詢操作，但我對更新操作感到困惑。這裏的報價：

我們做出以下觀察：當我們生成的 節點相關聯的時間間隔我們路過，我們可以覆蓋整個間隔[P + 1，Y]通過從節點 開始p + 1和爬第一棵樹（圖2.1）。因此，我們不需要對每個節點進行查詢，而是更新我們的 ，我們通過一次爬樹來即時計算查詢結果。 [ - 1，X，P]通過從 節點p開始 -

類似地，我們可以更新形式的所有時間間隔1和攀登第二樹（圖2.2）。 同時更新兩棵樹。

我懷疑它應該是倒過來：用於找到的最小間隔[P + 1，Y]，我們應該使用第二樹代替所述第一個的;爲找到最小間隔[x，p-1]，我們應該使用第一棵樹代替。

我的問題是：我是否正確？如果不是，有人可以舉一個簡單的例子來演示更新操作的工作方式嗎？

Answer 1

該解釋有點含糊。我想他們的意思是[p+1,y]你從p+1開始爬上前三個，但用第二個樹來查詢。

讓我們假設您更新第10個索引的值（來自紙張）。在更新樹時，您必須回答[x, 10 - 1] & [10 + 1, y]的查詢。爲了有效地做到這一點，你建兩個「爬」名單：

CLB1由p+1攀爬第一棵樹：攀登[11..11]，第二棵樹

CLB2的[12..15]：{11, 12}，其對應於下一個區間從p-1第二棵樹：{9, 8}，其對應於下一個時間間隔：[9..9]，第一棵樹

現在你開始第一樹通過爬上第一棵樹STA更新的[1..8]與10

10 rting - 平凡的更新

12 - 您需要查詢[9..9]，{10}，[11..11]，{12}。通過參加CLB2的第一個成員，您可以從BIT1獲得[9..9]的答案。並通過CLB1的第一個成員從BIT2獲得[11..11]的答案。 {10}和{12}是微不足道的。

16 - 您需要查詢[1..9]。 {10},[11..15]（沒有{16}，因爲它是虛構的）。您從BIT1拍下[1..9]，拍下前兩項CLB2。您拍下[11..15]，從BIT2開始，拍下前兩項CLB1。 {10}是微不足道的。

正如你可以看到左邊的查詢你從第二棵樹的p-1使用攀爬歷史記錄中的第一棵樹得到答案。對於正確的查詢，您可以使用第一棵樹的p+1的攀登歷史記錄從第二棵樹中獲取答案。

類似的過程用於更新右樹。

更新：過程第九節點

在更新9日指數情況下，我們有下一個CLB S：

CLB1：{10, 12}，間隔：[10..11]的BIT2[12..15]。

CLB2：{8}，間隔：的BIT1

[1..8]更新BIT1：

9 - 瑣碎

10 - 瑣碎（我們只需要{9}和{10}）

12 - 我們需要來自CLB1的第一項 - [10..11]和{12}與{9}

16 - 我們需要CLB1兩個第一項 - [10..11] U [12..15]，從CLB2第一個條目 - [1..8]和{9}

更新BIT2：

9 - 平凡

8 - 我們需要先CLB1 - [10..11] U [12..15]和{9}兩個條目與{8}

0 - 我們需要CLB1前兩個條目 - [10..11] U [12..15]和CLB2第一項 - [1..8]和{9}