使用樹狀數組的前綴和數組更新，查詢K的下界

首要序列總和陣列是一個集合，它累積交錯元素的總和，直到達到特定的索引。這是一種廣泛應用於組合重構以優化時間複雜度的策略。樹狀數組，也被稱為二進位索引樹（BIT），是一種高效地更新元素並在對數時間複雜度內計算前序列總和的資料庫形式。

在本文中，我們將討論如何使用C 中的Fenwick Tree進行現代化改進，以從一個系列求和數組中揭示給定值的較小極限邊界，這個值被稱為K。

文法

語法定義了兩個函數，update和query，以及一個用於Fenwick樹的主函數，Fenwick樹是一種用於高效範圍查詢和更新操作的資料結構。 update函數接受一個索引idx，一個值val，數組的大小n，以及Fenwick樹數組BIT。它透過將val加入索引idx及其所有祖先的節點來更新Fenwick樹。 query函數接受一個索引idx和Fenwick樹數組BIT。它傳回從根節點到索引idx的節點的累積和。主函數宣告數組的大小n，前綴和數組arr，以及初始化為0的Fenwick樹數組BIT。

void update(int idx, int val, int n, int BIT[]) {
   while (idx <= n) {
      BIT[idx] += val;
      idx += (idx & -idx);
   }
}
int query(int idx, int BIT[]) {
   int sum = 0;
   while (idx > 0) {
      sum += BIT[idx];
      idx -= (idx & -idx);
   }
   return sum;
}
// Driver code
int main() {
   int n; 
   int arr[n+1];
   int BIT[n+1] = {0}; 
   return 0;
}

演算法

要確定帶有Fenwick樹更新的前綴和數組中K的最小值，請按照以下複雜的步驟進行 -

• 實例化大小為 n 1 的 Fenwick 樹 (BIT)，將所有元素初始化為 0。

• 使用 update() 函數修改具有給定前綴和陣列的 Fenwick Tree。

• 在Fenwick樹上執行查詢以確定K的下界。從n的二進位表示中的最高有效位元開始迭代，直到最低有效位元。使用query()函數驗證目前前綴和是否小於或等於K。如果滿足此條件，將當前前綴和從K中減去，並更新索引以移動到下一個位元。如果不滿足條件，則在不更新索引的情況下移動到下一個位元。

• 遍歷完所有位元後，索引將表示前綴和陣列中 K 的下界。

• 輸出所得到的索引作為K的下界。

方法

• 方法1 − 在Fenwick樹上進行二分查找。在這種方法中，我們在Fenwick樹上執行二分查找以找到K的下界。

• 方法2 - 在Fenwick樹上進行帶有延遲傳播的二分查找。

方法 1

為了解決這個問題，我們首先將左指標和右指標分別設定為1和n（表示前綴和陣列的大小），然後採用二分查找策略來確定對應於小於或等於K的最大前綴和的索引i。然後，根據前綴和[i]的值是否小於或等於K，更新左指標或右指標的位置。

範例

這段程式碼的基本機制是利用了一種叫做 Fenwick Tree（也稱為 Binary Indexed Tree）的資料結構。它的作用是在前綴和數組中確定指定值 'k' 的下界。這是透過使用更新函數建立 Fenwick Tree 來實現的，該函數將前綴和數組中每個元素的值合併到 Fenwick Tree 的相應位置中。

findLowerBound 函數接著採用二分搜尋演算法，透過查詢函數來找出前綴和陣列中「k」的下界。此函數計算直至 Fenwick 樹中目前索引的值的累積和。最終，程式碼最終識別出前綴和陣列中「k」下界的索引，並將結果顯示到控制台。

#include <iostream>
using namespace std;
void update(int i, int v, int n, int b[]) {
    while (i <= n) {
        b[i] += v;
        i += (i & -i);
    }
}
int query(int i, int b[]) {
    int s = 0;
    while (i > 0) {
        s += b[i];
        i -= (i & -i);
    }
    return s;
}
int findLowerBound(int k, int n, int p[], int b[]) {
    int l = 1, r = n, idx = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        int msum = query(m, b);
        if (msum <= k) {
            idx = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return idx;
}
int main() {
    int n = 5;
    int p[] = {0, 1, 3, 6, 10, 15};
    int b[n + 1] = {0};
    for (int i = 1; i <= n; i++) {
        update(i, p[i], n, b);
    }
    int k = 10, idx;
    idx = findLowerBound(k, n, p, b);
    cout << "The lower bound of " << k << " is at index " << idx << " in the prefix sum array." << endl;
    return 0;
}

輸出

The lower bound of 10 is at index 3 in the prefix sum array.

方法2

為了進一步優化 Fenwick 樹，可以採用一種稱為惰性傳播的技術。這種方法需要將對 Fenwick Tree 的更新推遲到實際需要時，從而減少更新次數並提高查詢過程的效率。

範例

程式碼提供了一種解決方案，用於在前綴和陣列中定位給定值K的下限。前綴和數組是一個數組，其中每個元素都是原始數組中從索引0到該索引的元素的總和。下限是前綴和陣列中第一個使得到該索引的元素總和等於或超過K的索引。此解決方案使用Fenwick樹資料結構和延遲傳播技術來增強解決方案的效率。程式碼包括修改Fenwick樹、計算前綴和和找出下限的函數。程式碼還初始化了前綴和數組、Fenwick樹和延遲傳播數組。最後，它輸出了前綴和數組中K的下限。

#include  <iostream>
#include  <cstring>
using namespace std;

void update(int idx, int val, int n, int ft[], int lz[]) {
   while (idx  <= n) ft[idx] += val, idx += (idx & -idx);
}

int getPrefixSum(int idx, int ft[]) {
   int sum = 0;
   while (idx > 0) sum += ft[idx], idx -= (idx & -idx);
   return sum;
}

int findLowerBound(int K, int n, int ps[], int ft[], int lz[]) {
   int l = 1, r = n, lb = 0;
   while (l  <= r) {
      int m = (l + r) / 2, s = getPrefixSum(m, ft) + lz[m];
      if (s  <= K) lb = m, l = m + 1;
      else r = m - 1;
   }
   return lb;
}

int main() {
   int n = 5;
   int ps[] = {0, 1, 3, 6, 10, 15};
   int ft[n + 1], lz[n + 1]; memset(ft, 0, sizeof(ft)); memset(lz, 0, sizeof(lz));
   for (int i = 1; i  <= n; i++) update(i, ps[i] - ps[i - 1], n, ft, lz);
   int K = 10;
   int lb = findLowerBound(K, n, ps, ft, lz);
   cout << "For the given array with size " << n << " and prefix sum array [";
   for (int i = 1; i <= n; i++) {
      cout << ps[i];
      if (i < n) cout << ", ";
   }
   cout << "], the lower bound of " << K << " is at index " << lb << " in the prefix sum array." << endl;
   return 0;
}

輸出

For the given array with size 5 and prefix sum array [1, 3, 6, 10, 15], the lower bound of 10 is at index 4 in the prefix sum array.

結論

關於從精心設計的前綴和數組中挖掘難以捉摸的 K 值閾值的討論，並透過更新進行強化，利用 C 程式設計領域中巧妙的芬威克樹演算法。深入研究兩種高效方法的複雜性：Fenwick 樹上的二分搜尋和帶有惰性傳播的 Fenwick 樹上的二分搜尋。根據您的特定難題的特定要求和限制，仔細選擇最合適的方法。希望這能夠闡明這一難以捉摸的任務的概念化和實現，即利用 C 領域中 Fenwick 樹無與倫比的功能，從帶有更新的前綴和數組中找到 K 的下界。

以上是使用樹狀數組的前綴和數組更新，查詢K的下界的詳細內容。更多資訊請關注PHP中文網其他相關文章！