没有更新的范围总和查询的C ++程序？

在这里，我们将看到如何获取数组中从索引i到索引j的元素总和。这基本上是范围查询。只需从索引i到j运行一个循环，然后计算总和，即可轻松完成此任务。但是我们必须担心这种范围查询将被多次执行。因此，如果我们使用上述方法，则将花费大量时间。为了以更有效的方式解决这个问题，我们首先可以得到累加和，然后可以在恒定时间内找到范围和。让我们看一下获得想法的算法。

算法

rangeSum(arr,i,j)

begin
   c_arr := cumulative sum of arr
   if i = 0, then
      return c_arr[j];
      return c_arr[j] – c_arr[i-1]
end

示例

#include<iostream>
using namespace std;
void cumulativeSum(int c_arr[], int arr[], int n){
   c_arr[0] = arr[0];
   for(int i = 1; i<n; i++){
      c_arr[i] = arr[i] + c_arr[i-1];
   }
}
int rangeSum(int c_arr[], int i, int j){
   if( i == 0){
      return c_arr[j];
   }
   return c_arr[j] - c_arr[i-1];
}
main() {
   int data[] = {5, 4, 32, 8, 74, 14, 23, 65};
   int n = sizeof(data)/sizeof(data[0]);
   int c_arr[n];
   cumulativeSum(c_arr, data, n); //get cumulative sum
   cout << "Range sum from index (2 to 5): " << rangeSum(c_arr, 2, 5) << endl;
   cout << "Range sum from index (0 to 3): " << rangeSum(c_arr, 0, 3) << endl;
   cout << "Range sum from index (4 to 7): " << rangeSum(c_arr, 4, 7) << endl;
}

输出结果

Range sum from index (2 to 5): 128
Range sum from index (0 to 3): 49
Range sum from index (4 to 7): 176