তিনি এবং তার সাঙ্গোপাঙ্গরা রাজ্যের সকল গণিত সমস্যা সমাধানের জন্য বিখ্যাত ছিলেন। কিন্তু একদিন রাজ্যের একটি গ্রাম থেকে অভিযোগ এল যে, গ্রামের সকল সদস্য একটি বড় তালিকা নিয়ে সমস্যায় পড়েছে। তারা চায় তালিকার যেকোনো অংশের যোগফল দ্রুত বের করতে, কিন্তু তালিকা বড় হওয়ার কারণে তারা এটি করতে প্রচুর সময় নিচ্ছে।
যোগরাজা চিন্তায় পড়লেন, কীভাবে তিনি এই সমস্যার সমাধান করবেন? রাজ্যের গণিতবিদরা এমন একটি কৌশল চাচ্ছিলেন যা দ্রুত ফলাফল এনে দেবে।
● Prefix Sum-এর জাদুতত্ত্ব :
অনেক চিন্তা-ভাবনার পর যোগরাজা একটি কৌশল আবিষ্কার করলেন, যার নাম তিনি দিলেন "Prefix Sum"। সবাইকে ডেকে তিনি কৌশলটি বললেন, “আমাদের বারবার একই সংখ্যাগুলো যোগ করার দরকার নেই। আমরা একটি নতুন পদ্ধতি ব্যবহার করব, যার নাম হবে "Prefix Sum"। এতে প্রতিটি সংখ্যার যোগফল ধীরে ধীরে সংরক্ষণ করা হবে এবং পরে নির্দিষ্ট দুটি অবস্থানের মধ্যে থাকা সংখ্যাগুলোর যোগফলও দ্রুত বের করা যাবে।”
● বাস্তব জীবনের উদাহরণ - গ্রামের ধানের গোলা :
গণিতবিদ রাজ্যের একটি গ্রামে পাঁচটি ধানের গোলা আছে। প্রতিটি গোলায় ধান মজুদ করা হয় এবং সেই ধানের পরিমাণ যথাক্রমে 10, 20, 15, 25 এবং 30 কেজি। গ্রামের প্রধান ধানের মোট পরিমাণ বের করতে চান। তিনি প্রতিটি গোলার ধান এক এক করে যোগ করতে থাকেন। কিন্তু প্রতি বছর গোলার সংখ্যা বাড়তেই থাকে এবং এটি করতে তার অনেক সময় লাগতে শুরু করে।
এমন সময়, প্রধানের সহকারী তাকে বললেন, "প্রধান মশাই, আমরা প্রতিটি গোলার জন্য যোগরাজা'র তত্ত্ব অনুসারে একটি Prefix Sum তৈরি করতে পারি। এতে আপনি যখনই চান, নির্দিষ্ট দুটি গোলার মধ্যেও ধানের পরিমাণ দ্রুত জানতে পারবেন।"
এবার, গ্রাম প্রধান একটি Prefix Sum তালিকা তৈরি করলেন:
• প্রথম গোলা: 10 কেজি
• দ্বিতীয় গোলা: 10 + 20 = 30 কেজি
• তৃতীয় গোলা: 30 + 15 = 45 কেজি
• চতুর্থ গোলা: 45 + 25 = 70 কেজি
• পঞ্চম গোলা: 70 + 30 = 100 কেজি
এখন, যদি প্রধান মশাই জানতে চান ২য় থেকে ৪র্থ গোলার মধ্যে কত কেজি ধান আছে, তিনি শুধু ৪র্থ গোলার Prefix Sum থেকে ১ম গোলার Prefix Sum বিয়োগ করলেই ব্যস, তার পরিমাণও পেয়ে যাবেন:
• ৭০ - ১০ = ৬০ কেজি
● কোডের মাধ্যমে সমাধান :
যোগরাজা রাজ্যের বাকি গণিতজ্ঞদের জন্য Prefix Sum কৌশলটি একটি সি++ ম্যাজিকের মাধ্যমে দেখালেন:
C+#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,Q;
cin >> N >> Q; // অ্যারে এর সাইজ এবং কুয়েরি এর সংখ্যা ইনপুট নেওয়া হলো vector<long long int> V(N);
for(int i=0; i<N; i++)
{
cin >> V[i]; // অ্যারে এর ভ্যালুগুলো ইনপুট নেওয়া হলো
}
vector<long long int> prefix_sum(N);
prefix_sum[0] = V[0]; // প্রিফিক্স সাম অ্যারে এর প্রথম ভ্যালু হবে অ্যারে এর প্রথম ভ্যালুটি
for(int i=1; i<N; i++)
{
prefix_sum[i] = prefix_sum[i-1] + V[i]; // প্রতিটি ইন্ডেক্সে আগের ইন্ডেক্সের যোগফল যুক্ত হবে
}
for(int i=0; i<Q; i++)
{
int L,R;
cin >> L >> R;
L--;
R--; // ০ ভিত্তিক ইনডেক্সে রূপান্তর করছে
long long int SUM = 0;
if(L == 0)
{
SUM = prefix_sum[R]; // যদি L এর মান ০ হয় তবে L-1 invalid হয়ে যাবে। সেইক্ষেত্রে শুরু থেকে নিয়ে R পর্যন্ত হবে সাম
}
else
{
SUM = prefix_sum[R] - prefix_sum[L-1]; // নির্দিষ্ট L এবং R এর মধ্যে ভ্যালু গুলোর যোগফল বের করবে
}
cout << SUM << endl; // ফলাফল আউটপুট হবে
}
}
রাজ্যের গণিতজ্ঞরা এই কোড দেখে মুগ্ধ হয়ে গেলেন। তারা বুঝতে পারলেন, কীভাবে Prefix Sum কৌশল তাদের কাজ সহজ করে দিবে। এরপর থেকে Prefix Sum-এর জাদুতে রাজ্যে এধরণের সকল সমস্যার সমাধান দ্রুত এবং কার্যকরভাবে করা সম্ভব হলো।
● শিক্ষণীয় কথা :
গণিতবিদ রাজ্যের সকলেই শিখল, কখনো কখনো সমাধান খোঁজার জন্য আগাম পরিকল্পনা করা প্রয়োজন। যোগরাজা যেমন "Prefix Sum" ব্যবহার করে তাদের এমন একটি কৌশল শেখাল যা দিয়ে গণিতের জটিল সমস্যাও সহজে সমাধান করা যায়। তারা বুঝল Prefix Sum একটি সহজ কিন্তু শক্তিশালী কৌশল, যা অ্যারের সাথে কাজ করা অনেক সহজ করে দেয়। আর এটি শুধু গাণিতিক সমস্যার সমাধান নয় বরং বাস্তব জীবনের সমস্যাগুলোকেও সমাধান করতে পারে, যেমন গ্রামের ঐ ধানের হিসাব রাখা।
পরিশেষে, তারা সবাই রাজ্যের মহাজ্ঞানী যোগরাজাকে ধন্যবাদ জানাল, এই অসাধারণ কৌশলটি তাদেরকে শিখিয়েছেন জন্য। এভাবেই গণিতবিদ রাজ্যে Prefix Sum-এর জাদুতে সমস্যার সমাধান হলো এবং সেই দিন থেকে গণিতজ্ঞরা নতুন কৌশল আবিষ্কারের জন্য আরও আগ্রহী হয়ে উঠল।+ code:
