資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 的無更新範圍求和查詢
在本文中，我們將給出大小為 n 的陣列，它將是一個整數。然後，我們將計算從索引 L 到索引 R 的元素的總和，並多次執行查詢，或者我們需要計算給定範圍 [L, R] 的總和。例如 -
Input : arr[] = {1, 2, 3, 4, 5}
L = 1, R = 3
L = 2, R = 4
Output : 9
12
Input : arr[] = {1, 2, 3, 4, 5}
L = 0, R = 4
L = 1, R = 2
Output : 15
5查詢解決方案的方法
這個問題有兩個解決方案。第一個是透過蠻力方法和字首和（高效）方法。
蠻力方法
在這種方法中，我們將遍歷給定的範圍並列印總和。
示例
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // size of given array.
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
for(int i = L1; i <= R1; i++) // traversing through the first range.
sum += arr[i];
cout << sum << "\n";
sum = 0;
for(int i = L2; i <= R2; i++) // traversing through the second range.
sum += arr[i];
cout << sum << "\n";
}輸出
9 12
上述程式碼的解釋
在這種方法中，我們只是遍歷給定的範圍；在這種情況下，此程式很好，因為它具有搜尋時間複雜度 O(N)，其中 N 是給定陣列的大小。但是，當我們給出多個查詢 Q 時，這種情況會發生變化，我們的複雜度變為 O(N*Q)，其中 Q 是查詢數量，N 是給定陣列的大小。不幸的是，這種時間複雜度無法處理更高的約束，因此現在我們將研究一種適用於更高約束的高效方法。
高效方法
在這種方法中，我們將建立一個名為 prefix 的新陣列，它將是我們的字首和陣列，然後我們回答給定的範圍總和。
示例
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // size of given array.
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
int prefix[n];
for(int i = 0; i < n; i++){
sum += arr[i];
prefix[i] = sum;
}
if(L1) // to avoid segmentation fault
cout << prefix[R1] - prefix[L1 - 1] << "\n";
else
cout << prefix[R1] << "\n";
if(L2) // avoiding segmentation fault.
cout << prefix[R2] - prefix[L2 - 1] << "\n";
else
cout << prefix[R2] << "\n";
}輸出
9 12
上述程式碼的解釋
在這種方法中，我們將字首和值儲存在一個名為 prefix 的陣列中。現在，此陣列使我們的程式非常高效，因為它使我們的搜尋時間複雜度為 O(1)，這是您可以獲得的最佳複雜度，因此當我們給出 Q 個查詢時，我們的搜尋時間複雜度變為 O(Q)，其中 Q 是查詢數量。
結論
在本文中，我們解決了一個問題，即使用字首和陣列查詢無更新的範圍求和查詢。我們還學習了此問題的 C++ 程式以及解決此問題的完整方法（普通和高效）。我們可以在其他語言（如 C、Java、Python 和其他語言）中編寫相同的程式。希望本文對您有所幫助。
更新於：2021 年 11 月 26 日
358 次檢視
廣告