Partial Sum ব্যবহার করে সাধারণত দুই ধরণের সমস্যার সমাধান করা যায় ।
১) একটি Array এর কিছু অংশের যোগফল নির্ণয় বিষয়ক সমস্যা । এ ধরণের সমস্যাগুলোর সমাধান একই হয় ।তাই শুধু একটা সমস্যার সমাধান জানলেই চলে ।
ধরে নিই,n সাইজের একটা Array আছে যার উপাদানগুলো হচ্ছে a1, a2, ...an । এই Array এর উপর কিছু অপারেশন করতে হবে । প্রতিটি অপারেশনে দুইটা নাম্বার l এবং r দেওয়া থাকবে । আমাদের l থেকে r পর্যন্ত উপাদানগুলোর যোগফল বের করতে হবে । অর্থাৎ al + al + 1 + ... + ar ।
সাধারনভাবে আমরা লুপ চালিয়েই কাজটা করে ফেলতে পারি । কিন্তু প্রতিটি অপারেশনের জন্য প্রতিবার লুপ চালিয়ে কাজটা করা ঝামেলা ।এই কাজটা আমরা খুব সহজে করে ফেলবো Partial Sum ব্যবহার করে ।
আমরা একটা Array নিবো যার উপাদানগুলো হচ্ছে s1, s2, ..., sn । এখন আমরা প্রতিটি si উপাদানের জন্য si = a1 + a2 + ... + ai সেভ করে রাখবো । এই কাজটা একটা লুপ চালিয়েই করা যায় ।
এখন প্রতিটি অপারেশনের জন্য আমাদের উত্তর হবে sr - sl - 1 ।
২) ধরে নিই,n সাইজের একটা Array আছে যার উপাদানগুলো হচ্ছে a1, a2, ...an । আগের মত এই Array এর উপর কিছু অপারেশন করতে হবে । এবার প্রতিটি অপারেশনে তিনটা নাম্বার l , r ,v দেওয়া থাকবে । আমাদের l থেকে r পর্যন্ত সবগুলো উপাদানের সাথে v যোগ করতে বের করতে হবে । এমন কিছু অপারেশনের পর ফাইনাল Array টা প্রিন্ট করে দেখাতে হবে ।এটাও আমরা লুপ চালিয়েই করে ফেলতে পারি । কিন্তু যদি Array এর সাইজ এবং অপারেশনের সংখ্যা উভয়ই যদি 105 হয় তবে অবশ্যই টাইম লিমিট এক্সিড হয়ে যাবে । কারন 105 টি অপারেশনের জন্য যদি l=1 এবং r=105 হয়,তবে প্রতিবার 105 সাইজের Array আমাদের Traverse করতে হবে । তার মানে আমাদের মোট 1010 বার লুপ চালাতে হবে,যা সময় সাপেক্ষ ।
এই সমস্যার খুব সুন্দর এবং সহজ একটা সমাধান আমরা Partial Sum দিয়ে করে ফেলতে পারি ।
আমরা একটা Array নিবো যার উপাদানগুলো হচ্ছে p1, p2, ..., pn । প্রথমে আমরা এই Array এর প্রতিটি উপাদান ০ (শুন্য) করে দিবো । এখন প্রতিটি অপারেশনের জন্য pl এর মান v করে বাড়াবো এবং pr + 1 এর মান v করে কমাবো ।
এখন (১) এর পদ্ধতি অবলম্বন করে একটা লুপ চালিয়ে pi = pi + pi - 1 বের করে ফেলবো ।
এবার আমাদের ফাইনাল Array টা হবে a1 + p1, a2 + p2, ..., an + pn ।
১) একটি Array এর কিছু অংশের যোগফল নির্ণয় বিষয়ক সমস্যা । এ ধরণের সমস্যাগুলোর সমাধান একই হয় ।তাই শুধু একটা সমস্যার সমাধান জানলেই চলে ।
ধরে নিই,n সাইজের একটা Array আছে যার উপাদানগুলো হচ্ছে a1, a2, ...an । এই Array এর উপর কিছু অপারেশন করতে হবে । প্রতিটি অপারেশনে দুইটা নাম্বার l এবং r দেওয়া থাকবে । আমাদের l থেকে r পর্যন্ত উপাদানগুলোর যোগফল বের করতে হবে । অর্থাৎ al + al + 1 + ... + ar ।
সাধারনভাবে আমরা লুপ চালিয়েই কাজটা করে ফেলতে পারি । কিন্তু প্রতিটি অপারেশনের জন্য প্রতিবার লুপ চালিয়ে কাজটা করা ঝামেলা ।এই কাজটা আমরা খুব সহজে করে ফেলবো Partial Sum ব্যবহার করে ।
আমরা একটা Array নিবো যার উপাদানগুলো হচ্ছে s1, s2, ..., sn । এখন আমরা প্রতিটি si উপাদানের জন্য si = a1 + a2 + ... + ai সেভ করে রাখবো । এই কাজটা একটা লুপ চালিয়েই করা যায় ।
এখন প্রতিটি অপারেশনের জন্য আমাদের উত্তর হবে sr - sl - 1 ।
২) ধরে নিই,n সাইজের একটা Array আছে যার উপাদানগুলো হচ্ছে a1, a2, ...an । আগের মত এই Array এর উপর কিছু অপারেশন করতে হবে । এবার প্রতিটি অপারেশনে তিনটা নাম্বার l , r ,v দেওয়া থাকবে । আমাদের l থেকে r পর্যন্ত সবগুলো উপাদানের সাথে v যোগ করতে বের করতে হবে । এমন কিছু অপারেশনের পর ফাইনাল Array টা প্রিন্ট করে দেখাতে হবে ।এটাও আমরা লুপ চালিয়েই করে ফেলতে পারি । কিন্তু যদি Array এর সাইজ এবং অপারেশনের সংখ্যা উভয়ই যদি 105 হয় তবে অবশ্যই টাইম লিমিট এক্সিড হয়ে যাবে । কারন 105 টি অপারেশনের জন্য যদি l=1 এবং r=105 হয়,তবে প্রতিবার 105 সাইজের Array আমাদের Traverse করতে হবে । তার মানে আমাদের মোট 1010 বার লুপ চালাতে হবে,যা সময় সাপেক্ষ ।
এই সমস্যার খুব সুন্দর এবং সহজ একটা সমাধান আমরা Partial Sum দিয়ে করে ফেলতে পারি ।
আমরা একটা Array নিবো যার উপাদানগুলো হচ্ছে p1, p2, ..., pn । প্রথমে আমরা এই Array এর প্রতিটি উপাদান ০ (শুন্য) করে দিবো । এখন প্রতিটি অপারেশনের জন্য pl এর মান v করে বাড়াবো এবং pr + 1 এর মান v করে কমাবো ।
এখন (১) এর পদ্ধতি অবলম্বন করে একটা লুপ চালিয়ে pi = pi + pi - 1 বের করে ফেলবো ।
এবার আমাদের ফাইনাল Array টা হবে a1 + p1, a2 + p2, ..., an + pn ।
0 মন্তব্য(গুলি):
একটি মন্তব্য পোস্ট করুন