সমষ্টিগত যোগফল(Cumulative Sum) | Prefix Sum | Suffix Sum

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

সমস্যা ১

একটি অ্যারে {৫ -২ ৩ ৯ ৪ ৮} দিয়ে বলা হলো ২ নাম্বার এলিমেন্ট থেকে ৫ নাম্বার এলিমেন্ট পর্যন্ত -২ ৩ ৯ ৪ সব গুলোর যোগফল কত? L = 2 এবং R = 5 হলে L থেকে R পর্যন্ত লুপ চালিয়ে যোগফল ১৪ বের করে ফেলতে পারি খুব সহজেই। সবথেকে খারাপ কেইসে এর কমপ্লেক্সিটি হতে পারে O(n); এখানে, n হচ্ছে অ্যারে সাইজ। কিন্তু, যদি বলা হয় বিভিন্ন রেঞ্জের যোগফল দেখতে চাই। মানে Q বার দেখতে চাই,

void PrefixSum(int ar[], int n, int Q) {   while (Q--) {     int L, R;     cin >> L >> R;     int sum = 0;     // as array start with index zero, that’s why     // we should start L-1 and stop when i==R-1     for (int i = L-1;i <= R-1;i++) {       sum += ar[i];     }     cout << sum << endl;   } }

Q এর লিমিট n এর সমান হলে কিন্তু সবথেকে খারাপ কেইসে কমপ্লেক্সিটি হয়ে যাবে O(n^2); যেটি খুব একটা ভালো কমপ্লেক্সিটি না। যোগফল বের করার কাজটি যদি O(1) এ করে ফেলতে পারি তাহলে কিন্তু কমপ্লেক্সিটি একেবারেই কমে যাচ্ছে। কমপ্লেক্সিটি হবে O(Q); যেটি কিনা O(n^2); এর তুলনায় খুবই নগণ্য। কিন্তু, এই কাজ টি করব কীভাবে?

সমাধান

সমাধান কিন্তু খুব সহজ, অ্যারে {৫ -২ ৩ ৯ ৪ ৮} এর প্রথম ঘরে ৫ ই থাকবে, দ্বিতীয় ঘরে ৫ এবং -২ এর যোগফল ৩ বসিয়ে দিব, তৃতীয় ঘরে আগের দুইটির যোগফল এবং বর্তমান পজিশনের এলিমেন্টের সাথে যোগ করে রেখে দিব। এভাবে চলবে। তাহলে যোগফল গুলো রাখার পর অ্যারে টি হবে, {৫ ৩ ৬ ১৫ ১৯ ২৭}। এইভাবে যোগ করে রেখে দেওয়াকেই বলে কিউমুলেটিভ সাম। প্রথম দুইটি এলিমেন্টের যোগফল, প্রথম তিনটি এলিমেন্টের যোগফল, প্রথম চারটি এলিমেন্টের যোগফল ইত্যাদি যোগফল গুলো কে বলে হয় প্রিফিক্স। এখন এই কিউমুলেটিভ সাম বা প্রিফিক্স সাম আমাদের কীভাবে কাজে লাগতে পারে? আমি যদি ২ থেকে ৫ নাম্বার পর্যন্ত এলিমেন্ট গুলোর যোগফল বের করতে চাই তাহলে এখন খুব সহজেই বের করতে পারব। ৫ নাম্বার ঘরে আছে ১৯। আর এই ১৯ থেকে ২ নাম্বার ঘরের আগের ঘরের প্রিফিক্স সাম বাদ দিয়ে দিব, ১৯ - ৫ = ১৪!!! তাহলে রেঞ্জ যদি হয় L এবং R, ans = PrefSum[R] - PrefSum[L-1];

চিত্রে অ্যারের ইনডেক্স ০ থেকে শুরু হয়েছে এবং আমি উপরে উদাহরণ দিয়েছি ১ কে প্রথম ইনডেক্স ধরে। এটি নিয়ে আশাকরছি কনফিউশন থাকবে না। এবং অবশ্যই একটু সতর্ক থাকবেন।

এবার প্রোগ্রাম লিখার পালা। যদিও ধরে নিচ্ছি, এ পর্যন্ত এসে প্রোগ্রাম টি আপনি করে ফেলতে পারবেন তবুও আমি সমাধান টির সম্পূর্ণ কোড না দিয়ে প্রিফিক্স সাম বের করা পর্যন্ত কোড দিয়ে দিচ্ছি। তবে অবশ্যই প্রোগ্রাম দেখার আগে নিজে চেষ্টা করে নিবেন। 

void PrefixSum(int ar[], int n) {   int PrefSum[n];   for (int i = 0;i < n;i++) {     PrefSum[i] = 0;   }   // start summing from front   PrefSum[0] = ar[0];   for (int i = 1;i < n;i++) {     PrefSum[i] = PrefSum[i-1] + ar[i];   }   // print Prefixes   for (int i = 0;i < n;i++) {     cout << PrefSum[i] << ' ';   }   cout << endl; }

সমস্যা টি সাফিক্স সাম দিয়েও সমাধান করা যায়। প্রিফিক্স সামের সময় আমরা কি করতাম? বাম পাশে থেকে ডান পাশে যোগ করে করে যেতাম। সাফিক্স সামেও একই কাজ তবে ডান পাশে থেকে বাম পাশে যোগ করে করে আসতে হয়। আপনার কাজ, এখন এই সমস্যা টি সাফিক্স সাম দিয়েও সমাধান করা।

সমস্যা ২

একটি ১০ সাইজের অ্যারে আছে আপনার কাছে। সবগুলো পজিশনে ০ দিয়ে ইনিশিয়ালাইজ করা আছে, {০ ০ ০ ০ ০ ০ ০ ০ ০ ০ }। এখন আপনি চাইলেন L থেকে R পর্যন্ত পজিশন গুলোতে ২ যোগ করবেন। ধরে নিলাম L = 1, R = 5 এবং value = 2। তাহলে এখন অ্যারে টি হবে এমন, {২ ২ ২ ২ ২ ০ ০ ০ ০ ০}। এই কাজ টিও আমরা লুপ চালিয়ে প্রতি ঘরে ২ যোগ করে সহজেই করে ফেলতে পারি। আরো দুইটি কুয়েরি দিয়ে দেখি, L = 3, R = 10 এবং value = 1। তাহলে এখন অ্যারে টি হবে এমন, {২ ২ ৩ ৩ ৩ ১ ১ ১ ১ ১}। আবার, L = 7, R = 8 এবং value = 1। তাহলে এখন অ্যারে টি হবে এমন, {২ ২ ৩ ৩ ৩ ১ ২ ২ ১ ১}। কিন্তু, আপনি নিশ্চয়ই বুঝে গিয়েছেন প্রতিবার লুপ চালানো টা আসলে ভালো কমপ্লেক্সিটি নয়। আবারো কমপ্লেক্সিটি O(n^2) হয়ে যাবে। আগের মত O(1) কি রেঞ্জ গুলো কোন ভাবে পূর্ণ করা সম্ভব?

সমাধান

প্রিফিক্স বা সাফিক্স সামের আইডিয়া কি কাজ করবে? এই সমস্যা তে কাজ করবে না। তবে, প্রিফিক্স সামের একটু মডিফাই ভার্শন কাজ করবে। আইডিয়া টি হচ্ছে L তম পজিশনে value যোগ করে রাখব এবং R+1 তম পজিশনে value বিয়োগ করে রাখব। বাকি পজিশন গুলো তে আমার এখনই আর কোন কাজ নেই এবং কাজ টি O(1); এই হয়ে যাচ্ছে। যেমন, L = 1, R = 5 এবং value 2 হলে, {2 0 0 0 0 -2 0 0 0 0}। পরের কুয়েরি, L = 3, R = 10 এবং value 1 হলে, {2 0 1 0 0 -2 0 0 0 0}। যেহেতু ১০ এর পরে কোন পজিশন নেই তাই এই কেইসে বিয়োগ না করলেও চলবে। তবে যেহেতু, পজিশন নেই সেহেতু, R+1 তম পজিশনে value বিয়োগ করতে গেলে কিন্তু প্রোগ্রামের মাথা খারাপ হয়ে যাবে। এক্ষেত্রে অ্যারে তে n এর থেকে একটি পজিশন বেশি নিয়ে রাখলে চিন্তা নেই। পরের কুয়েরি, L = 7, R = 8 এবং value 1 হলে, {2 0 1 0 0 -2 1 0 -1 0}। এভাবে সবগুলো কুয়েরি শেষ হলে, আমি এখন প্রিফিক্স বা কিউমুলেটিভ সামের মত যোগ করে সহজেই যোগফল পেয়ে যাচ্ছি, {2 2 3 3 3 1 2 2 1 1}!!!

আশাকরছি চিত্র টি দেখার পর বিষয় টি আরো পরিস্কার হয়ে গেছে। এখন, অ্যারের কোন পজিশনে কত যোগ হয়েছে, তা কিন্তু খুব সহজে O(1); সময়েই বের করে ফেলতে পারবেন।

সম্ভবত প্রোগ্রাম এখন একাই লিখে ফেলতে পারবেন। না পারলে আবার পড়ে একটু চেষ্টা করেন। আমি অ্যারের ফাইনাল অবস্থা পর্যন্ত প্রোগ্রাম লিখে দিয়ে দিচ্ছি। প্রোগ্রাম দেখার আগে অবশ্যই একটু চেষ্টা করে নিবেন এবং নিজে নিজে পারলেও পরে প্রোগ্রাম টি দেখে নিবেন।

void CumuSum() {   int n, q;   cin >> n >> q;   // initialize all the index with zero   int dp[n+2] = {0};   while (q--) {     int L, R, value;     cin >> L >> R >> value;     // add the value to the left     dp[L] += value;     // decrease the R+1 th position so that     // value will be added only in the range between L and R     dp[R+1] -= value;   }   // Cumulative sum start. As dp[0] = 0; so,   // we don’t need to worry about it.   for (int i = 1;i <= n;i++) {     dp[i] += dp[i-1];   }   // print the final state.   for (int i = 1;i <= n;i++) {     cout << dp[i] << ' ';   }   cout << endl; }

প্র্যাক্টিস প্রবলেম
Counting Pretty Numbers
KJ and street lights