在本文中,我们将给出一个大小为 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和其他语言)编写相同的程序。希望你觉得这篇文章有帮助。