এখানে আমরা দেখব কীভাবে একটি অ্যারেতে ইনডেক্স 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); // ক্যুমুলেটিভ সম বের করুন
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
