没有更新的范围总和查询的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