資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用稀疏表進行 C++ 範圍求和查詢
稀疏表是一種資料結構，用於提供範圍查詢的結果。它可以在 O(logN) 的複雜度內提供大多數範圍查詢的結果。對於最大範圍查詢，它也可以在 O(1) 內計算結果。
本教程將討論使用稀疏表進行範圍求和查詢的問題，其中給定一個數組。我們需要找到例如範圍 L 和 R 中所有元素的總和。
Input: arr[ ] = { 2, 4, 1, 5, 6, 3 }
query(1, 3),
query(0,2),
query(1, 5).
Output: 10
7
19
Input: arr[ ] = { 1, 2, 3, 4, 1, 4 }
query(0, 2),
query(2,4),
query(3, 5).
Output: 6
8
9查詢解決方案的方法
首先，我們需要建立一個稀疏表來在其中搜索答案。在建立稀疏表時，我們使用一個二維陣列來儲存答案。在稀疏表中，我們將查詢分解成 2 的冪。建立稀疏表後，我們在該表中搜索查詢，並在滿足 (Left_index + 2^n - 1 <= Right_index) 條件時將值持續新增到變數中，其中 n 是二維陣列列的大小。
示例
以上方法的 C++ 程式碼
#include <bits/stdc++.h>
using namespace std;
// Maximum value of row of sparse table.
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// query to be found with the help of a sparse table.
long long query(int l, int r){
long long sum = 0;
for (int i = n; i >= 0; i--) {
if (l + (1 << i) - 1 <= r) {
sum = sum + SPARSE[l][i];
l += 1 << i;
}
}
return sum;
}
int main(){
int arr[] = { 1, 2, 3, 4, 1, 4 };
int z = sizeof(arr) / sizeof(arr[0]);
// Building sparse table.
for (int i = 0; i < z; i++)
SPARSE[i][0] = arr[i];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= z - (1 << j); j++)
SPARSE[j][i] = SPARSE[j][i - 1] + SPARSE[j + (1 << (i - 1))][i - 1];
cout <<"Sum: " << query(0, 2) << endl;
cout <<"Sum: " << query(2, 4) << endl;
cout <<"Sum: " << query(3, 5) << endl;
return 0;
}輸出
Sum: 6 Sum: 8 Sum: 4
結論
在本教程中，我們討論了建立稀疏表，這對範圍查詢非常有用。我們討論了一種簡單的解決此問題的方法，即透過建立稀疏表並從該表中獲取查詢結果。我們還討論了此問題的 C++ 程式，我們也可以使用 C、Java、Python 等程式語言來實現。希望本教程對您有所幫助。
更新於: 2021-11-26
245 次檢視
廣告