使用C++翻译以下内容：无更新的区间求和查询-C++-PHP中文网

使用C++翻译以下内容：无更新的区间求和查询

PHPz

发布： 2023-09-10 12:41:02

转载

1062 人浏览过

使用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

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
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";
}

登录后复制