資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用樹狀陣列更新字首和陣列查詢 K 的下界
字首和陣列是一個累加到特定索引的所有連續元素的總和的陣列。它是一種廣泛用於陣列重構以改進時間複雜度的技術。樹狀陣列，也稱為二進位制索引樹 (BIT)，是一種資料結構，可以有效地更新元素並以對數時間複雜度計算字首和。
在本文中，我們將討論如何在 C++ 中使用樹狀陣列更新從字首和陣列中找到給定值（稱為 K）的下界。
語法
語法定義了兩個函式，update 和 query，以及樹狀陣列的主函式，樹狀陣列是一種用於高效範圍查詢和更新操作的資料結構。update 函式接收索引 idx、值 val、陣列大小 n 和樹狀陣列 BIT。它透過將 val 新增到索引 idx 處的節點及其所有祖先來更新樹狀陣列。query 函式接收索引 idx 和樹狀陣列 BIT。它返回從根節點到索引 idx 處的節點的所有節點的累積和。主函式宣告陣列大小 n、字首和陣列 arr 和樹狀陣列 BIT，它初始化為 0。
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;
}
演算法
要確定帶有樹狀陣列更新的字首和陣列中 K 的最小值，請遵循以下複雜步驟：
例項化一個大小為 n+1 的樹狀陣列 (BIT)，並將所有元素初始化為 0。
使用 update() 函式使用給定的字首和陣列修改樹狀陣列。
對樹狀陣列執行查詢以確定 K 的下界。從 n 的二進位制表示中的最高位開始，並從該位迭代到最低位。使用 query() 函式檢查當前字首和是否小於或等於 K。如果滿足此條件，則從 K 中減去當前字首和並更新索引以移動到下一位。如果不滿足，則移動到下一位而不更新索引。
遍歷所有位後，索引將表示字首和陣列中 K 的下界。
輸出獲得的索引作為 K 的下界。
方法
方法 1 - 在樹狀陣列上進行二分查詢。在這種方法中，我們在樹狀陣列上執行二分查詢以找到 K 的下界。
方法 2 - 使用延遲傳播在樹狀陣列上進行二分查詢。
方法 1
為了解決這個問題，我們首先將左指標和右指標分別設定為 1 和 n（表示字首和陣列的大小）。並使用二分查詢策略來識別對應於小於或等於 K 的最大字首和的索引 i。然後，我們根據 prefix_sum[i] 的值是否小於或等於 K 來更新左指標或右指標的位置。
示例
此程式碼的基本機制是使用樹狀陣列，也稱為二進位制索引樹。它的目的是確定字首和陣列中指定值（表示為“k”）的下界。這是透過使用 update 函式構造樹狀陣列來完成的，該函式將字首和陣列中每個元素的值合併到樹狀陣列中的相應位置。
然後，findLowerBound 函式使用二分查詢演算法透過使用 query 函式來精確定位字首和陣列中“k”的下界。此函式計算樹狀陣列中直到當前索引的值的累積和。最終，程式碼以識別字首和陣列中“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
為了進一步最佳化樹狀陣列，可以使用一種稱為延遲傳播的技術。這種方法需要推遲對樹狀陣列的更新，直到它們真正需要，從而減少更新次數並提高查詢過程的效率。
示例
該程式碼提供了一種解決方案，用於在給定字首和陣列中找到給定值 K 的下限。字首和陣列是一個數組，其中每個元素構成原始陣列中直到該索引（包括該索引）的所有元素的總和。下限是字首和陣列中的第一個索引，其中直到該索引的所有元素的總和等於或超過 K。該解決方案使用樹狀陣列資料結構和延遲傳播技術來提高解決方案的效率。該程式碼包含用於修改樹狀陣列、計算字首和以及查詢下限的函式。該程式碼還初始化字首和陣列、樹狀陣列和延遲傳播陣列。最後，它輸出字首和陣列中 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.
結論
本文討論瞭如何在 C++ 程式設計領域中，使用巧妙的樹狀陣列演算法，從經過精心設計的包含更新的字首和陣列中找到值 K 的難以捉摸的閾值。深入探討了兩種高效方法：在樹狀陣列上進行二分查詢以及使用延遲傳播在樹狀陣列上進行二分查詢。根據特定難題的具體需求和約束，仔細選擇最合適的方法。希望這能闡明從包含更新的字首和陣列中查詢 K 的下界的概念化和實現，利用樹狀陣列在 C++ 領域中無與倫比的力量。
124 次瀏覽
