数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告