প্রিফিক্স সাম কি?
প্রিফিক্স সাম হল একটি অ্যালগোরিদম, যা একটি অ্যারের উপাদানগুলোর যোগফল সংরক্ষণের একটি পদ্ধতি। এটি ব্যবহার করে, আমরা যেকোনো সাবঅ্যারে তে যোগফল বের করতে পারি অতি দ্রুত সময়ে।
প্রিফিক্স সাম কেন ব্যবহার করা হয়?
ধরি, আপনার কাছে একটি অ্যারে রয়েছে: [1, 2, 3, 4, 5]. এখন আপনি চাইতেছেন, arr[l] থেকে arr[r] পর্যন্ত যোগফল বের করতে। আপনি চাইলে অন্যভাবে খুব সহজেই করতে পারবেন কিন্তু অনলাইন জাজে Time Limit Exceed(TLE) খেতে পারেন। আর এই সমস্যা খুব সহজেই আপনি প্রিফিক্স সামের সাহায্যে সমাধান করতে পারবেন।
প্রিফিক্স সাম ব্যবহার না করলে আপনাকে প্রতি বার লুপ চালাতে হয়। কিন্তু যদি প্রিফিক্স সাম ব্যবহার করেন তাহলে একবার হিসাব করে, পরবর্তী সময়গুলোতে আপনি মাত্র O(1) সময়ে কাজটি করতে পারবেন।
প্রিফিক্স সামের সুবিধা :
প্রিফিক্স সামের সুবিধা হল যে এটি একবার অ্যারের উপাদানগুলোর যোগফল হিসাব করে সংরক্ষণ করে। যার পরবর্তী সময়ে সাবঅ্যারের যোগফল বের করার জন্য আমাদের সময় O(1) থাকে।
যেমনঃ, প্রিফিক্স সাম তৈরি করতে সময় লাগবে O(n), এবং সাবঅ্যারের যোগফল বের করতে O(1) সময় লাগে।
প্রিফিক্স সাম গণনার উদাহরণ :
C++ উদাহরণ
#includeusing namespace std; int main() { int arr[] = {1, 2, 3, 4, 5}; int n = 5; int prefix[n]; prefix[0] = arr[0]; // প্রথম উপাদান কপি করছি for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; // প্রতিটি উপাদান যোগ করতে থাকছি } cout << "Prefix Sum Array: "; for (int i = 0; i < n; i++) { cout << prefix[i] << " "; // আউটপুট: 1 3 6 10 15 } return 0; }
Python উদাহরণ
def prefix_sum(arr):
prefix = [0] * len(arr)
prefix[0] = arr[0] # প্রথম উপাদান কপি করছি
for i in range(1, len(arr)):
prefix[i] = prefix[i - 1] + arr[i] # প্রতিটি উপাদান যোগ করতে থাকছি
return prefix
arr = [1, 2, 3, 4, 5]
print("Prefix Sum Array:", prefix_sum(arr)) # আউটপুট: [1, 3, 6, 10, 15]
কিভাবে সাবঅ্যারের যোগফল বের করা যাবে?
যদি আপনি জানেন যে আপনার প্রিফিক্স সাম অ্যারে তৈরি হয়ে গেছে, তাহলে আপনার সাবঅ্যারের যোগফল O(1) সময়ে বের করা যাবে। এই কোডটি দেখুন:
C++ উদাহরণ
int rangeSum(int prefix[], int l, int r) {
if (l == 0) return prefix[r];
return prefix[r] - prefix[l - 1]; // সাবঅ্যারের যোগফল বের করা
}
Python উদাহরণ
def range_sum(prefix, l, r):
if l == 0:
return prefix[r]
return prefix[r] - prefix[l - 1] # সাবঅ্যারের যোগফল বের করা
প্রিফিক্স সামের সুবিধা ও প্রয়োগ
প্রিফিক্স সামের সবচেয়ে বড় সুবিধা হলো, আপনি একবার যোগফল হিসাব করে সংরক্ষণ করে ফেললে, পরবর্তীতে সাবঅ্যারের যোগফল বের করতে মাত্র O(1) সময়ে কাজ করতে পারবেন। এতে আপনার প্রোগ্রাম আরও দ্রুত কাজ করবে।
প্রিফিক্স সাম ব্যবহার করে আপনি বিভিন্ন ধরনের সমস্যা যেমন, সাবঅ্যারের যোগফল, সাবঅ্যারের গড় বের করা, এবং অন্যান্য সংখ্যাসূচক সমস্যা সমাধান করতে পারবেন।
0 comments:
Post a Comment