使用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和其他語言）編寫相同的程式。希望你覺得這篇文章有幫助。

以上是使用C++翻譯以下內容：無更新的區間求和查詢的詳細內容。更多資訊請關注PHP中文網其他相關文章！