প্রোগ্রামিং প্রব্লেম সল্ভিং এর খুব beginner level এর একটি topic হচ্ছে prefix sum technique. এটি সহজ একটি technique, কিন্তু advanced অনেক সমস্যায় এ এটি কাজে লাগে।
ধরি, আমাদেরকে একটি integer array দেওয়া আছে। এবার একটি index-range [L,R] (যেখানে L<=R) দিয়ে বলা হলো, এই range এর মধ্যে যেসব element আছে তাদের যোগফল বের করতে। আমরা মাথায় যেটা আসে যে, একটি লুপ ব্যবহার করে array এর L তম element থেকে R তম element পর্যন্ত traverse করবো এবং এদের যোগফলকে একটি variable এ store করে print করে দিবো।
এখন যদি এ ধরনের query একটি না থেকে অনেক গুলো থাকে, তবে কি প্রতিটি query এর জন্যই আমরা এভাবে একবার করে লুপ চালাবো? না! একটি smart technique আছে, যাকে আমরা prefix sum বা cumulative sum বলি। আমরা এখন সেটি দেখবো।
প্রথমে আমাদের prefix sum array বানাতে হবে। এই array এর i তম element হবে given array এর প্রথম i সংখ্যক element এর যোগফল। আমরা একটি লুপ চালিয়েই নিচের মতো করে এই কাজটি করতে পারি।
কোডে prefixSum[i] বের করার সময় আগের ধাপে বের করে রাখা prefixSum[i-1] এর সাথে arr[i] যোগ করে দিলেই হচ্ছে। তাহলে O(n) time complexity তে আমাদের prefixSum array টি তৈরি হয়ে গেল।
এবার একটু খেয়াল করলে আমরা দেখবো, prefixSum[R] এ array এর index 1 থেকে R পর্যন্ত element গুলোর যোগফল store করে রাখা আছে। আবার prefixSum[L-1] এ array এর index 1 থেকে L-1 পর্যন্ত element গুলোর যোগফল store করে রাখা আছে। এখন আমরা যদি prefixSum[R] থেকে prefixSum[L-1] কে বিয়োগ করি, তাহলেই তো index L থেকে R পর্যন্ত element গুলোর যোগফল পেয়ে যাচ্ছি, তাই না?
অর্থাৎ কোন query এর জন্য আমরা একটি মাত্র বিয়োগ operation করেই উত্তর দিয়ে দিতে পারছি। পূর্বের পদ্ধতিতে n size এর array আর m সংখ্যক query এর জন্য আমাদের program এর time complexity হতো O(n*m). আর এখন prefixSum array বানানোর জন্য time complexity লাগলো O(n) এবং m সংখ্যক query এর প্রতিটির answer আমরা দিতে পারছি O(1) এ। ফলে পুরো প্রোগ্রামের time complexity দাঁড়ায় O(n+m).
SPOJ এর CSUMQ - Cumulative Sum Query (link: https://www.spoj.com/problems/CSUMQ/ ) সমস্যাটি হুবহু একই সমস্যা। আমরা তাহলে একটু চেষ্টা করে কোড লিখে সমস্যাটির সমাধান করে ফেলবো।
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন