Prefix Sum পরিচিতি

আগের সলিউশন টা নিয়ে চিন্তা করে দেখলে আমরা দেখতে পারি এখানে প্রাইমারি লুপ যেটা দিয়ে আমরা কুয়েরি গুলা উত্তর করছি তা কোন ভাবেই কমানো পসিবল না। এবং এই লুপ টা চালালে আমার given time complexity এর মধ্যে প্রোগ্রামটি রান করবে। এখানে যে লুপটি আসলে প্রবলেম ক্রিয়েট করছে তা হলো কুয়েরি এর ভিতরের লুপ যার দ্বারা আমরা যোগফল বের করতেছিলাম। এই লুপ টা কীভাবে বাদ দেয়া যায় আসেন তা নিয়ে একটু চিন্তা করি।

এই প্রবলেমটি সমাধান করতে হলে আমাদের একটি নতুন টেকনিক সম্পর্কে জানতে হবে। এই টেকনিকের নাম প্রিফিক্স সাম টেকনিক। যার মাধ্যমে আমরা একটি এরে এর একটি নির্দিষ্ট রেঞ্জের যোগ ফল শুধু মাত্র O(1) টাইম কমপ্লেক্সিটি তে বলে দিতে পারবো।

প্রিফিক্স সাম টেকনিক মুলত একটি প্রিফিক্স সামের এরে তৈরি করে যেখানে প্রিফিক্স সামের প্রতিটি ইন্ডেক্স i এ, অরিজিনাল এরে এর 0 থেকে i পর্যন্ত সকল ইন্ডেক্সের ভ্যালু এর যোগফল স্টোর করা থাকবে।

একটি এরে এর উদাহরণের মাধ্যমে দেখার চেষ্টা করি বিষয়টা।

Origina Array	5	5	2	3
Prefix Sum Array	5	10	12	15
Index	0	1	2	3

উক্ত এরে এর জন্য কিছু কুয়েরি দিয়ে উত্তর টা বের করার মাধ্যমে প্রিফিক্স সাম টেকনিক কীভাবে কাজ করছে দেখার চেষ্টা করি।

যদি আমাকে জিজ্ঞেস করা হয়

১। অরিজিনাল এরে এর Ar[0] থেকে Ar[3] পর্যন্ত ভ্যালু গুলার যোগফল কতো। তাহলে আমরা প্রিফিক্স সাম এরে এর 3 নাম্বার ইন্ডেক্স এর ভ্যালু বলে দিলে হয়ে যাবে যা হলো ১৫ । কারণ আমরা জানি প্রিফিক্স সামের এরে এর 3rd index এ অরিজিনাল এর ০ থেকে ৩ নাম্বার পর্যন্ত ইন্ডেক্সের যোগফল আছে অর্থাৎ Prefix_sum_array[3] = ar[0] + ar[1] + ar[2] +ar[3] .

২। যদি জিজ্ঞেস করা হয় এরে এর 2 নাম্বার ইন্ডেক্স পর্যন্ত ভ্যালু গুলার যোগফল কতো তবে তা আমরা প্রিফিক্স সাম এরে এর ২ নাম্বার ইন্ডেক্স দেখলে পেয়ে যাবো, কারণ Prefix_sum_array[2] = ar[0] + ar[1] + ar[2] =12

৩। যদি জিজ্ঞেস করা হয় এরে এর 1 নাম্বার ইন্ডেক্স পর্যন্ত ভ্যালু গুলার যোগফল কতো তবে তা আমরা প্রিফিক্স সাম এরে এর 1 নাম্বার ইন্ডেক্স দেখলে পেয়ে যাবো, কারণ Prefix_sum_array[1] = ar[0] + ar[1] = 10

৪। এখন যদি আমাদের বলা হয় , এরে এর প্রথম থেকে নিয়ে কোন একটি নির্দিষ্ট ইনডেক্সের যোগফল নয় বরং একটি নির্দিষ্ট ইন্ডেক্স থেকে অপর একটি নির্দিষ্ট ইনডেক্সের যোগফল যদি চাওয়া হয় , তবে তা কীভাবে করবো । আসুন , একটি উদাহরণের সাহায্যে দেখার চেষ্টা করি।

ধরুন বলা হলো এরে এর 2 নাম্বার ইনডেক্স থেকে 3 নাম্বার ইনডেক্স এর যোগফল কতো ? খেয়াল করলে দেখবেন , Prefix_sum_array[3] = ar[0] + ar[1] + ar[2] +ar[3] অর্থাৎ প্রিফিক্স সাম এরে এর ইনডেক্স ৩ তে ০ থেকে নিয়ে ৩ নাম্বার ইনডেক্সের সব ভ্যালু যোগ করা আছে। এখন আমরা যদি চাই এরে এর ২ নাম্বার ইনডেক্স থেকে ৩ নাম্বার ইনডেক্সের মান বের করতে তবে আমাদের ar[0] + ar[1] এই অংশটুকু বাদ দিতে হবে। আবার , Prefix_sum_array[1] = ar[0] + ar[1] এ স্টোর আছে । তার মানে ২ থেকে ৩ নাম্বার ইন্ডেক্সের যোগফল = Prefix_sum_array[3] - Prefix_sum_array[1] = ar[0] + ar[1] + ar[2] +ar[3] - ar[0] + ar[1] = ar[2] +ar[3] যা আমাদের ২ এবং ৩ নাম্বার ইনডেক্সের ভ্যালুর যোগফল ।

আমাদের যদি জিজ্ঞেস করা হয় কোন একটি এরে এর L তম ইনডেক্স থেকে R তম ইন্ডেক্সের ভ্যালু গুলার যোগফল কতো , তবে আমরা খুব সহজে প্রিফিক্স সাম এর এরে থেকে তা বলে দিতে পারবো , তা হলো Sum (L,R) = Prefix_sum_array[R] - Prefix_sum_array[L-1]