C++ 程序用于无更新的范围和查询?
server side programmingprogrammingc++
在这里我们将看到如何获取数组中从索引 i 到索引 j 的元素之和。这基本上是范围查询。只需从索引 i 到 j 运行一个循环并计算总和，任务就很简单。但我们必须注意这种范围查询将执行多次。因此，如果我们使用上述方法，将花费大量时间。要使用更有效的方法解决这个问题，我们可以首先获得累积总和，然后可以在恒定时间内找到范围总和。让我们看看算法来获得这个想法。
算法
rangeSum(arr, i, j)
begin c_arr := 累积总和 arr 如果 i = 0，则 返回 c_arr[j]; 返回 c_arr[j] – c_arr[i-1] 结束
示例
#include<iostream>
using namespace std;
voidcumulativeSum(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); //获取累计和
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
