এখানে আমরা দেখব কিভাবে একটি অ্যারেতে index i থেকে index 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
