এই নিবন্ধে, আমরা n আকারের একটি অ্যারে দেব, যা একটি পূর্ণসংখ্যা হবে। তারপর, আমরা সূচক L থেকে সূচক R পর্যন্ত উপাদানগুলির যোগফল গণনা করব এবং একাধিকবার প্রশ্নগুলি সম্পাদন করব, অথবা আমাদের [L, R] থেকে প্রদত্ত পরিসরের যোগফল গণনা করতে হবে। যেমন −
Input : arr[] = {1, 2, 3, 4, 5}
L = 1, R = 3
L = 2, R = 4
Output : 9
12
Input : arr[] = {1, 2, 3, 4, 5}
L = 0, R = 4
L = 1, R = 2
Output : 15
5 সমাধান খোঁজার পদ্ধতি
এই প্রশ্নের দুটি সমাধান আছে। প্রথমটি হল ব্রুট ফোর্স পদ্ধতি এবং উপসর্গ যোগফল(দক্ষ) পদ্ধতির মাধ্যমে।
ব্রুট ফোর্স অ্যাপ্রোচ
এই পদ্ধতিতে, আমরা প্রদত্ত পরিসীমা অতিক্রম করব এবং যোগফল প্রিন্ট করব।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // size of given array.
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
for(int i = L1; i <= R1; i++) // traversing through the first range.
sum += arr[i];
cout << sum << "\n";
sum = 0;
for(int i = L2; i <= R2; i++) // traversing through the second range.
sum += arr[i];
cout << sum << "\n";
} আউটপুট
9 12
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা কেবল প্রদত্ত রেঞ্জের মধ্য দিয়ে যাচ্ছি; এই ক্ষেত্রে, এই প্রোগ্রামটি ভাল কারণ এতে অনুসন্ধানের সময় জটিলতা রয়েছে O(N), যেখানে N হল প্রদত্ত অ্যারের আকার। তারপরও, এই পরিবর্তন হয় যখন আমাদেরকে বেশ কয়েকটি প্রশ্ন Q দেওয়া হয় তখন আমাদের জটিলতা O(N*Q) এ পরিণত হয়, যেখানে Q হল প্রশ্নের সংখ্যা এবং N হল প্রদত্ত অ্যারের আকার। দুর্ভাগ্যবশত, এই সময় জটিলতা উচ্চ সীমাবদ্ধতাগুলি পরিচালনা করতে পারে না, তাই এখন আমরা একটি দক্ষ পদ্ধতির দিকে নজর দেব যা উচ্চ সীমাবদ্ধতার জন্য কাজ করবে৷
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা উপসর্গ নামে একটি নতুন অ্যারে তৈরি করব যা হবে আমাদের প্রিফিক্স সমষ্টি অ্যারে, এবং তারপর আমরা প্রদত্ত ব্যাপ্তির যোগফলের উত্তর দেব।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // size of given array.
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
int prefix[n];
for(int i = 0; i < n; i++){
sum += arr[i];
prefix[i] = sum;
}
if(L1) // to avoid segmentation fault
cout << prefix[R1] - prefix[L1 - 1] << "\n";
else
cout << prefix[R1] << "\n";
if(L2) // avoiding segmentation fault.
cout << prefix[R2] - prefix[L2 - 1] << "\n";
else
cout << prefix[R2] << "\n";
} আউটপুট
9 12
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা উপসর্গের সমষ্টির মানগুলিকে উপসর্গ নামক অ্যারেতে সংরক্ষণ করি। এখন, এই অ্যারেটি আমাদের প্রোগ্রামটিকে অত্যন্ত দক্ষ করে তোলে কারণ এটি আমাদের O(1) এর অনুসন্ধানের সময় জটিলতা দেয়, যা আপনি পেতে পারেন এমন সেরা জটিলতা, এবং তাই যখন আমাদের Q পরিমাণ প্রশ্ন দেওয়া হয়, তখন আমাদের অনুসন্ধানের সময় জটিলতা O(এ পরিণত হয়) Q) যেখানে Q হল প্রশ্নের সংখ্যা।
উপসংহার
এই নিবন্ধে, আমরা প্রিফিক্স যোগ অ্যারে ব্যবহার করে আপডেট ছাড়াই রেঞ্জ সমষ্টির প্রশ্নগুলি খুঁজে পেতে একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
