使用樹狀數組（離線查詢），將範圍L到R中大於K的元素數量計算出來

在電腦科學領域，我們必須處理大型資料集，其中包括查詢選擇和更新操作。以較低的時間複雜度即時執行這些操作對於開發人員來說是一項具有挑戰性的任務。

使用 Fenwick 樹是解決這些基於範圍的查詢問題的有效方法。

Fenwick Tree 是一種資料結構，可以有效地更新元素並計算表中數字的前綴和。它也稱為二元索引樹。

在本文中，我們將討論如何使用 Fenwick 樹來找出 L 到 R 範圍內大於 K 的元素數量。

輸入輸出場景

假設您有一個包含 N 個元素的數組，並且您想要在數組中找到 L 到 R 範圍內大於 K 的元素數量。

Input: 
arr = {1, 15, 12, 13, 6, 18, 14, 10, 23, 41, 16, 9}
N = 11, K = 17, L = 1, R = 8
Output: 
2

什麼是離線查詢？

離線查詢是對預先決定的資料集執行的查詢操作。換句話說，這些操作僅對那些在處理查詢時沒有進一步修改的資料集執行。

使用芬威克樹

在這裡，我們將使用芬威克樹，它的每個節點都有向量，其中按順序包含數組的所有元素。然後，我們使用二分搜尋來回答每個查詢並計算元素的數量。

• 建立兩個函數，updateTree() 和total()，分別用於更新和檢索BIT中的前綴和。

• 接下來，建立另一個函數，該函數將計算 L 到 R 範圍內大於「K」的元素。函數接受輸入值「arr」、「N」、「L」、「R」和「K 」。

• 計數是用最大範圍N的累加和減去K的累加和來計算的。

為了排除超出範圍的元素，減去L-1的累加和（如果L大於1）。

範例

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

// Updating the Fenwick Tree
void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

// Counting the number of elements
int elementsGreaterThanK(vector<int>& arr, int N, int K, int L, int R) {
   vector<int> BIT(N+1, 0);

   for (int i = L; i <= R; i++) {
      updateTree(BIT, arr[i], 1);
   }

   int count = total(BIT, N) - total(BIT, K);
   if (L > 1) {
      count -= total(BIT, L-1);
   }
   return count;
}

int main() {
   vector<int> arr = {0, 5, 2, 3, 6, 8, 7, 1, 8, 4, 6, 9};
   int N = 11; // Total range of values
   int K = 4; // Highest value
   int L = 1; // Start index of the range
   int R = 8; // End index of the range

   int count = elementsGreaterThanK(arr, N, K, L, R);
   cout << "Number of elements greater than " << K << " in the range [" << L << ", " << R << "]: " << count << endl;

   return 0;
}

輸出

Number of elements greater than 4 in the range [1, 8]: 5

替代方法

在這裡，我們將建立一個單獨的向量來儲存查詢。每個查詢由兩個變數組成，index 和 val。 index 用於儲存陣列中的位置，而val用於儲存該索引處元素的值。這種方法使開發人員能夠執行各種查詢操作。此外，我們使用 BIT 計算每個查詢大於 K 的元素數量。

範例

#include <iostream>
#include <vector>
using namespace std;
struct Query {
   int index;
   int val;
};

void updateTree(vector<int>& BIT, int index, int value) {
   while (index < BIT.size()) {
      BIT[index] += value;
      index += index & -index;
   }
}

int total(vector<int>& BIT, int index) {
   int result = 0;
   while (index > 0) {
      result += BIT[index];
      index -= index & -index;
   }
   return result;
}

vector<int> elementsGreaterThanK(vector<int>& arr, vector<Query>& queries, int K) {
   int N = arr.size();
   vector<int> BIT(N+1, 0);
   vector<int> result;

   for (int i = 0; i < N; i++) {
      updateTree(BIT, i+1, (arr[i] > K) ? 1 : 0);
   }

   for (auto query : queries) {
      if (query.val > K) {
         result.push_back(total(BIT, query.index));
      }
      else {
         result.push_back(0);
      }
   }

   return result;
}

int main() {
   vector<int> arr = {3, 14, 32, 7, 11, 5, 8, 6, 16, 2, 15};
   vector<Query> queries = {{2, 4}, {5, 3}, {3, 6}, {0, 3}};
   int K = 2;

   vector<int> counts = elementsGreaterThanK(arr, queries, K);

   for (int count : counts) {
      cout << "Number of elements greater than " << K << ": " << count << endl;
   }

   return 0;
}

輸出

Number of elements greater than 2: 2
Number of elements greater than 2: 5
Number of elements greater than 2: 3
Number of elements greater than 2: 0

結論

我們可以簡單地從索引 L 到 R 迭代數組，並在每次數組元素大於 K 時加 1，以便找到每個查詢的答案。然而，為了降低時間複雜度，我們使用Fenwick樹來進行此類查詢操作。我們也可以使用線段樹和稀疏表來取代Fenwick樹來進行此類查詢操作。

以上是使用樹狀數組（離線查詢），將範圍L到R中大於K的元素數量計算出來的詳細內容。更多資訊請關注PHP中文網其他相關文章！