binary-indexed-tree

1熱度

2回答

如何使用二進制索引樹進行範圍更新，以使範圍內的每個元素A[k]均爲[i..j]更新爲A[k]*c，其中c是某個常數。而我需要做這樣的更新操作後點查詢。我試着用下面的函數，但它不工作，這裏n是數組的大小，c是我想乘以範圍的每個元素的常量。 def updateM(x, c, n): while x <= n: BIT[x] *= c x += (x & -x) ，這些都

0熱度

1回答

有人能給我提供二維二叉索引樹的算法嗎？

我在網上搜索，但找不到一個好的。我從geeksforgeeks.org獲得了一些幫助，但無法理解在更新BIT數組時從aux [i] [j]中減去v1-v2-v2-v4 + v3的構造部分。請讓我知道爲什麼我們在這裏扣除。 void constructAux(int mat[][N], int aux[][N+1]) { // Initialise Auxiliary array to

0熱度

1回答

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

基於此paper，我發現在O(lg N)中使用兩個BIT來完成RMQ是相當出色的，因爲它比段樹更容易編碼，而且該文章聲稱它性能也比其他數據結構好。我明白如何構建樹以及如何執行查詢操作，但我對更新操作感到困惑。這裏的報價：我們做出以下觀察：當我們生成的節點相關聯的時間間隔我們路過，我們可以覆蓋整個間隔[P + 1，Y]通過從節點開始p + 1和爬第一棵樹（圖2.1）。因此，我們不需要對每個節

0熱度

1回答

查找範圍與體重k個項目的數量（含更新和查詢）

我試圖解決以下問題：考慮到與整型權（任意順序）項目的數組，我們可以有2個可能的操作：查詢：輸出是權重k的項，在範圍x到y的數量。更新：在一定的索引換物品的重量到v 例：鑑於數組：[1,2,3,2,5,6,7,3 ] 如果我們查詢從索引1與權重2項至3的數，則答案是2. 如果我們在索引2修改元件以具有2的權重，那麼我們再次進行相同的查詢，答案將是3. 這當然是（用點更新）段樹問題。但是，

1熱度

1回答

範圍異或使用BIT或樹狀數組

對於整數的給定陣列總和，我們要計算XORed總和withing給定範圍[L, R]，通過XORed總和我的意思是Σ(Arr[i]^p)其中i:[L,R]和p是一些數。在計算XORed總和時，可以輕鬆完成此操作，直到數組中的每個i-th元素爲止。現在問題發生在p頻繁更改時。並重新計算XORed總和，直到每個i-th元素在這種情況下似乎都不是理想的解決方案。我想這可以使用fenwick tree或BI

7熱度

1回答

如何找到使用二進制索引樹（BIT）增加特定長度的子序列的總數

如何使用二進制索引樹（BIT）找到具有特定長度的增加子序列的總數？實際上這是從Spoj Online Judge 的問題實施例假設我有一個數組1,2,2,10 長度3是1,2,4和1,3,4 所以，答案的增加的子序列是2。

2熱度

1回答

使用BIT匹配的方括號

編輯：我試圖解決一個spoj問題。這裏是問題的鏈接： http://spoj.pl/problems/BRCKTS 我可以想出兩個可能的數據結構來解決問題一個使用分段樹，另一個使用BIT。我已經使用分段樹實現瞭解決方案。我看過一點，但我無法弄清楚如何用它做特定的事情（這是我下面提到）我想檢查是否括號是隻含有(一個給定的字符串中平衡's或)'s。我正在使用一個位（二進制索引樹）來解決問題。我

-1熱度

1回答

使用二叉索引樹進行字符串查詢

我想使用Fenwick樹範圍查詢一個字符串。但是我的代碼出了問題。級聯錯誤 Eror是：[Error]'operator + ='（操作數類型是'std :: vector>'和'std :: string {aka std :: basic_string}'）匹配給定一個字符串s ，我想把這個字符串存儲在這個fenwick樹中。例如S = ABCDEF，在BIT它謹（頂部 - 底部）A A

1熱度

1回答

二進制索引樹的應用

我試圖解決this算法的問題，我遇到了這個很好的解決方案：「我們的想法是對待一個我，B 我和 Ç我們使用c i作爲值， b i作爲關鍵字，它們按照公司的順序插入給我一個 i。此方式，對於每一個我反過來，該數據結構允許對C的最小值查詢Ĵ（可能∞）對於b Ĵ在[1..b 我）和一個 j < a i。我們有çĴ <Ç我當且僅當參賽者我不優秀。」 source 現在我有很難理解這一解決方案。這