二進制索引樹的應用

Question

我試圖解決this算法的問題，我遇到了這個很好的解決方案：

「我們的想法是對待一個_我，B _我和 Ç_{我們使用c i作爲值， b i作爲關鍵字，它們按照公司的順序插入給我一個 i。此 方式，對於每一個我反過來，該數據結構允許對C的 最小值查詢Ĵ（可能∞）對於b Ĵ在[1..b 我）和 一個 j < a i。我們有çĴ <Ç我當且僅當參賽者我不 優秀。」}

source

現在我有很難理解這一解決方案。

這裏是我理解這個解決方案：我知道二叉索引樹用於回答查詢，比如在數組中找到一個區間的總和，它也支持元素中的更新，它在O（logn）時間複雜度中執行兩個操作。 s解決方案表示，我們建立密鑰爲BIT，其密鑰爲c _i，並且值爲b _i，基本上b _i是附加值，與每個節點一起使用。現在，我們在樹中插入元素，增加值 _i，這是我失去抓地力的地方。我們插入節點的順序以及聲明在這個部分後面說的是什麼，我不知道。

請幫我理解這個解決方案是什麼意思。

Answer 1

讓我們找到所有非優秀的參與者。另一位參與者j只有在他的a[j] < a[i]時才能比參與者i更好。因此，我們可以忽略更大的a[j]值的所有參與者。這就是爲什麼我們按a對它們進行分類。

這種情況是必要的，但這還不夠。我們還需要檢查b和c。我們怎麼做到這一點？我們需要知道是否有一個人a[j] < a[i]（即，按照排序順序排在最前面的那個人），因此他的b[j] < b[i]和c[j] < c[i]。我們建立一個BIT（使用c[j]作爲鍵，b[j]是數值）來檢查最後兩個條件。很明顯，只有當前綴[0, c[i])的最小值小於b[i]時，j才存在。總結起來，這個想法如下：我們按a[i]對它們進行排序，然後忽略a的值。這樣，我們從一個三維問題轉向二維問題，這個問題更容易解決（這就是爲什麼順序很重要的問題，那個更大的問題從來都不會更好）。我們使用BIT來解決二維問題。