Ở đây chúng ta sẽ xem cách lấy tổng các phần tử từ chỉ số i đến chỉ số j trong một mảng. Về cơ bản đây là truy vấn phạm vi. Nhiệm vụ dễ dàng bằng cách chỉ chạy một vòng lặp từ chỉ số i đến j và tính tổng. Nhưng chúng ta phải quan tâm rằng loại truy vấn phạm vi này sẽ được thực thi nhiều lần. Vì vậy, nếu chúng tôi sử dụng phương pháp đã đề cập, nó sẽ mất nhiều thời gian. Để giải quyết vấn đề này bằng cách sử dụng hiệu quả hơn, chúng ta có thể nhận được tổng tích lũy lúc đầu, sau đó tổng phạm vi có thể được tìm thấy trong thời gian không đổi. Hãy để chúng tôi xem thuật toán để có được ý tưởng.
Thuật toán
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
Ví dụ
#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;
} Đầu ra
Range sum from index (2 to 5): 128 Range sum from index (0 to 3): 49 Range sum from index (4 to 7): 176