অ্যারে ও স্ট্রিংপড়তে ৫ মিনিট লাগবে

প্রিফিক্স সাম (Prefix Sums)

আগে থেকেই যোগফল হিসাব করে রাখা, যাতে যেকোনো সাব-অ্যারের যোগফল চোখের পলকে O(1) স্পিডে বের করা যায়

build time: O(n)query time (sum range): O(1)space: O(n)

ধরুন আপনি সারা বছর প্রতিদিন কত টাকা খরচ করেন তা লিখে রাখেন। এখন কেউ যদি জিগ্যেস করে, "১৫ তম দিন থেকে ৬০ তম দিন পর্যন্ত আপনার মোট কত খরচ হয়েছে?", সাধারণ বা বোকা পদ্ধতিতে বের করতে গেলে আপনাকে ওই ৪৫ দিনের সব খরচ আলাদা আলাদা করে যোগ করতে হবে। অর্থাৎ প্রতিটা প্রশ্নের জন্যই O(n) সময় নষ্ট হবে। যদি লাখ লাখ মানুষ আপনাকে এমন প্রশ্ন করে, তবে যোগ করতে করতেই আপনার জীবন শেষ হয়ে যাবে!

এর বদলে, আপনি একটা রানিং টোটাল অ্যারে (Running Total array) বানাতে পারেন, যাকে প্রিফিক্স সাম অ্যারে (Prefix Sum array)-ও বলা হয়। এর মানে হলো: প্রতিদিনের শেষে আপনি শুধু এটা লিখে রাখবেন যে, বছরের শুরু থেকে আজ পর্যন্ত আপনার মোট কত টাকা খরচ হয়েছে।

◈ Explore prefix sums

← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন

এটা কীভাবে কাজ করে (পেছনের অঙ্ক)

ধরি আপনার প্রতিদিনের খরচের অ্যারে হলো A = [২, ৪, ১, ৫, ৩]।

আপনি একটা প্রিফিক্স সাম অ্যারে P বানালেন, যার প্রতিটা উপাদান হলো A অ্যারের একদম শুরু থেকে ওই নির্দিষ্ট দিন পর্যন্ত সব খরচের যোগফল:

P[0] = A[0] = ২
P[1] = A[0]+A[1] = ৬
P[2] = A[0]+A[1]+A[2] = ৭
P[3] = A[0]+A[1]+A[2]+A[3] = ১২
P[4] = A[0]+A[1]+A[2]+A[3]+A[4] = ১৫

তাহলে আপনার প্রিফিক্স সাম অ্যারেটা দাঁড়াল: [২, ৬, ৭, ১২, ১৫]।

এবার হলো আসল ম্যাজিক। কেউ যদি প্রশ্ন করে: "ইনডেক্স ১ থেকে ইনডেক্স ৩ পর্যন্ত যোগফল কত?" (মূল A অ্যারেতে এটা হলো ৪ + ১ + ৫ = ১০)।

লুপ চালিয়ে বারবার যোগ করার কোনো দরকার নেই, শুধু প্রিফিক্স সাম অ্যারের দিকে তাকান! আপনি জানেন যে ইনডেক্স ৩ পর্যন্ত মোট খরচ P[3] = ১২। আর আপনি এটাও জানেন যে ইনডেক্স ১-এর আগে মোট খরচ ছিল P[0] = ২। এখন আপনি যদি "মোট খরচ" থেকে ওই "আগের খরচ" টুকু স্রেফ বিয়োগ করে দেন, তাহলেই পেয়ে যাবেন আপনার মাঝখানের নির্দিষ্ট অংশের যোগফল!

Sum(i থেকে j) = P[j] - P[i - 1]
Sum(১ থেকে ৩) = P[3] - P[0] = ১২ - ২ = ১০।

দেখলেন তো? চোখের পলকে মাত্র একটা বিয়োগ করেই উত্তর পেয়ে গেলেন! যার স্পিড হলো O(1)।

১-ইনডেক্সড অফসেট ট্রিক (The "1-Indexed Offset" Trick)

কোড লেখার সময় একটা ছোট্ট ঝামেলা হয়: যখন i এর মান ০ হয়, তখন P[i - 1] খুঁজতে গেলে P[-1] হয়ে যায় (যাকে "আউট অফ বাউন্ড" এরর বলে)। এই ঝামেলা এড়াতে বেশিরভাগ প্রোগ্রামাররা প্রিফিক্স সাম অ্যারের সাইজ মূল অ্যারের চেয়ে এক ঘর বড় করে নেন, এবং একদম শুরুতে একটা 0 বসিয়ে দেন।

যেমন: P = [০, ২, ৬, ৭, ১২, ১৫]

এখন অঙ্কটা আরও নিরাপদ ও ছিমছাম হয়ে যায়: Sum(i থেকে j) = P[j + 1] - P[i]।

দ্রষ্টব্য: প্রিফিক্স সাম ট্রিকটা স্ট্যাটিক বা অপরিবর্তনশীল অ্যারের ক্ষেত্রে সবচেয়ে ভালো কাজ করে, যখন মূল ডেটাগুলো আর চেঞ্জ হয় না এবং আপনাকে বারবার রেঞ্জ (Range) থেকে যোগফল বের করতে হয়। কিন্তু মূল অ্যারে যদি বারবার আপডেট হতে থাকে, তবে এই ট্রিক অনেক স্লো (O(n)) হয়ে যায়, কারণ একটা ডেটা চেঞ্জ হলেই পেছনের সব যোগফল আপডেট করতে হয়। বারবার আপডেট হওয়া অ্যারের জন্য 'সেগমেন্ট ট্রি' (Segment Tree) বা 'ফেনউইক ট্রি' (Fenwick Tree) ব্যবহার করা ভালো।