資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告