ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে আছে। আমাদের সূচক i থেকে j পর্যন্ত উপস্থিত উপাদানগুলির যোগফল খুঁজে বের করতে হবে। দুটি জিনিস আমাদের মনে রাখতে হবে যে অ্যারেটি অপরিবর্তনীয় হবে, তাই উপাদানগুলি পরিবর্তন করা হবে না এবং এই জাতীয় একাধিক প্রশ্ন থাকবে। তাই আমাদেরকে বিপুল সংখ্যক প্রশ্নের জন্য নির্বাহের সময় সম্পর্কে যত্ন নিতে হবে। ধরুন অ্যারেটি A =[5, 8, 3, 6, 1, 2, 5] এর মতো, তারপর যদি কোয়েরি হয় (A, 0, 3), তবে এটি 5 + 8 + 3 + 6 =22 হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি অ্যারে B নিন। B[i] 0 থেকে i পর্যন্ত উপাদানের যোগফল সংরক্ষণ করবে
- কোয়েরির জন্য B[j] – B[i – 1] সম্পাদন করুন
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class NumArray {
public:
vector <int> pre;
NumArray(vector<int>& nums) {
pre.clear();
int n = nums.size();
pre.resize(n);
for(int i = 0; i < n; i++){
if(i == 0)pre[0] = nums[0];
else
pre[i] = pre[i - 1] + nums[i];
}
}
int sumRange(int i, int j) {
if(i == 0)return pre[j];
return pre[j] - pre[i - 1];
}
};
main(){
vector<int> v = {5,8,3,6,1,2,5};
NumArray na(v);
cout<<na.sumRange(0,2)<<endl;
cout<<na.sumRange(2,5)<<endl;
cout<<na.sumRange(0,5)<<endl;
} ইনপুট
Initialize it with [5,8,3,6,1,2,5] Call sumRange(0,2) sumRange(2,5) sumRange(0,5)
আউটপুট
16 12 25
