資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用樹狀陣列（離線查詢）查詢區間 L 到 R 中大於 K 的元素個數
在計算機科學領域，我們必須處理大型資料集，這包括查詢選擇和更新操作。對於開發人員來說，以較低的時空複雜度即時執行這些操作是一項具有挑戰性的任務。
使用樹狀陣列是解決這些基於範圍的查詢問題的有效方法。
樹狀陣列是一種資料結構，它可以高效地更新元素並計算表中數字的字首和。它也稱為二進位制索引樹。
在本文中，我們將討論如何使用樹狀陣列查詢區間 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，以找到每個查詢的答案。但是，為了降低時間複雜度，我們對這種型別的查詢操作使用**樹狀陣列**。除了樹狀陣列之外，我們還可以使用**線段樹**和**稀疏表**來進行此類查詢操作。
瀏覽量：275
