fenwick-tree

    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
    algorithm xor fenwick-tree binary-indexed-tree 2017-03-20

    6熱度

    1回答

    範圍查詢爲O反轉的數目（LG N）

    給定n個整數的無序陣列，我知道我可以找到在O（N LG N）以下這種方法，使用比特反轉的總數：Count Inversion by BIT 然而，如果我必須查詢O（lg N）中總反轉次數的任意範圍，有可能嗎？ O（N lg N）預先計算是可以接受的。 我已經做了一些研究，似乎N因素是不可避免的... 任何建議，將不勝感激！
    algorithm data-structures segment-tree fenwick-tree 2015-04-28

    1熱度

    1回答

    將樹線性化爲數組並回答路徑上的「求和」查詢

    問題出在codechef中的travtree問題。在editorial，他們建議通過記錄每個節點在DFS遍歷中的發現和退出時間，將樹線性化到數組。現在我們可以快速回答有關sum subtree的查詢 - 通過對該節點的[discovery time, exit time]段中發生的事件進行求和。 （我們使用Fenwick樹來快速回答這些查詢）。 然而，要解決這個問題，我們還需要快速回答sum pa
    algorithm tree fenwick-tree 2016-07-23

    1熱度

    1回答

    範圍更新/查詢二進制索引樹

    問題陳述： https://www.hackerrank.com/contests/epiccode/challenges/square-array 鑑於整數數組A1，A2，... AN，你必須在陣列中執行兩種類型的 查詢。 1 x y。向Ax添加1×2，向Ax + 1添加2×3，向Ax + 2添加3×4，向Ax35添加4×5至 ，依次類推，直到Ay。 2 x y。找到從 指數x到指數y模109
    fenwick-tree 2015-06-22

    -1熱度

    1回答

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

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

    2熱度

    2回答

    如何找到哪個位置在BIT中有前綴總和M？

    假設我創建了一個前綴長度爲N的二進制索引樹。主陣列僅包含0 s和1 s。現在我想找到哪個索引有一個前綴總和M（這意味着正好有M 1 s）。 像我的數組是a[]={1,0,0,1,1}; 前綴和會是什麼樣{1,1,1,2,3}; 現在第三屆指數（0基於）具有2 前綴和我如何才能找到這個指數有幾分？ 在此先感謝。
    algorithm data-structures fenwick-tree 2017-04-05

    0熱度

    1回答

    Fenwick Tree中的不正確更新元素

    我編寫了一個程序，它通過獲取命令'給出一個範圍總和並通過命令'u'更新一個元素，但它工作不正確。 請幫助我。 #include <iostream> #include <vector> #include <fstream> using namespace std; template <typename indexT, typename valueT> class FenwickTree
    fenwick-tree 2014-12-20

    0熱度

    1回答

    具有條件的BIT中的範圍更新

    可以使用條件在BIT中執行範圍更新嗎？假設我有一個負數和正數頻率A [] = {1，-3，-4，5，9}。我想用範圍更新數組的值：如果更新值（x）爲負值，只更新負值元素，如果更新值爲正數，則只更新範圍中的正值。 例如，在上述數組中，如果更新查詢是2 4 -2（左邊的值），那麼只更新第2（-3）和第3（-4）位置。因爲它是一個正整數，所以留下4th（5）位置。 或者我應該使用另一個數據結構來完成這個
    segment-tree fenwick-tree 2015-07-11

    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
    c++ algorithm fenwick-tree binary-indexed-tree 2017-07-26

    0熱度

    1回答

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

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