不使用 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寻找解决方案的方法
这个问题有两种解决方案。第一个是蛮力方法和前缀sum(Efficient)方法。
蛮力方法
在这种方法中，我们将遍历给定的范围并打印总和。
示例
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); //给定数组的大小。
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
for(int i = L1; i <= R1; i++) //穿过第一个范围。
sum += arr[i];
cout << sum << "\n";
sum = 0;
for(int i = L2; i <= R2; i++) //穿过第二个范围。
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); //给定数组的大小。
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) //避免分段错误
cout << prefix[R1] - prefix[L1 - 1] << "\n";
else
cout << prefix[R1] << "\n";
if(L2) //避免分段错误。
cout << prefix[R2] - prefix[L2 - 1] << "\n";
else
cout << prefix[R2] << "\n";
}输出结果9 12
上面代码的解释
在这种方法中，我们将前缀和值存储在名为prefix的数组中。现在，这个数组使我们的程序非常高效，因为这使我们的搜索时间复杂度为O(1)，这是您可以获得的最佳复杂度，因此当我们获得Q查询量时，我们的搜索时间复杂度变为O(Q)Q是查询的数量。
结论
在本文中，我们解决了使用Prefixsum数组查找无需更新的Rangesum查询的问题。我们还学习了针对这个问题的C++程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用其他语言编写相同的程序，例如C、java、python和其他语言。希望这篇文章对您有所帮助。