数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新时间： 30-Jul-2019
254 次浏览
广告