এই আর্টিকেলে, আমরা একটি n আকারের পূর্ণসংখ্যা অ্যারে দিয়ে থাকব। তারপর আমরা সূচক 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); // দেওয়া অ্যারের আকার int L1 = 1, R1 = 3; int L2 = 2, R2 = 4; int sum = 0; for(int i = L1; i <= R1; i++) // প্রথম রেঞ্জ ট্রাভার্স sum += arr[i]; cout << sum << "\n"; sum = 0; for(int i = L2; i <= R2; i++) // দ্বিতীয় রেঞ্জ ট্রাভার্স sum += arr[i]; cout << sum << "\n"; }
আউটপুট
9 12
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা সিম্পলি দেওয়া রেঞ্জগুলো ট্রাভার্স করছি। এই কেসে প্রোগ্রামটি ভালো কাজ করে কারণ এর সার্চিং টাইম কমপ্লেক্সিটি O(N), যেখানে N হল অ্যারের আকার। কিন্তু যখন অনেক কোয়েরি Q দেওয়া থাকে, তবে কমপ্লেক্সিটি O(N*Q) হয়ে যায়, যা উচ্চ কনস্ট্রেইন্টের জন্য উপযুক্ত নয়। তাই আমরা দক্ষ পদ্ধতি দেখব।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা একটি নতুন অ্যারে prefix তৈরি করব যা আমাদের প্রিফিক্স সম অ্যারে হবে, এবং তারপর রেঞ্জের যোগফল বের করব।
উদাহরণ
#include<bits/stdc++.h> using namespace std; int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr)/sizeof(int); // দেওয়া অ্যারের আকার 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) // সেগমেন্টেশন ফল্ট এড়াতে cout << prefix[R1] - prefix[L1 - 1] << "\n"; else cout << prefix[R1] << "\n"; if(L2) // সেগমেন্টেশন ফল্ট এড়াতে cout << prefix[R2] - prefix[L2 - 1] << "\n"; else cout << prefix[R2] << "\n"; }
আউটপুট
9 12
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রিফিক্স সম মানগুলো prefix নামের একটি অ্যারেতে সংরক্ষণ করি। এই অ্যারে আমাদের প্রোগ্রামকে খুব দক্ষ করে তোলে কারণ এটি O(1) সার্চিং টাইম কমপ্লেক্সিটি দেয়, যা সেরা কমপ্লেক্সিটি। তাই Q সংখ্যক কোয়েরি দেওয়া থাকলে সার্চিং টাইম কমপ্লেক্সিটি হয় O(Q)।
উপসংহার
এই আর্টিকেলে, আমরা প্রিফিক্স সম অ্যারে ব্যবহার করে আপডেট ছাড়া রেঞ্জ সম কোয়েরি সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
