JavaScript-এ রিকারসন ব্যবহার করে প্রিফিক্স সম (Prefix Sums) অ্যারে তৈরি

ভূমিকা

প্রিফিক্স সম (Prefix Sums) বা কালেক্টিভ সম: একটি অ্যারের প্রতিটি ইন্ডেক্স থেকে শেষ পর্যন্ত এলিমেন্টগুলোর যোগফল বের করে একটি নতুন অ্যারে বানানো। উদাহরণ: `[10,5,6,12,7,1]` → `[41,31,26,20,8,1]`।

পদ্ধতি ১: Map + Reduce (ফাংশনাল, O(n²))

const arr = [10, 5, 6, 12, 7, 1];

const partSum = arr.map((item, index) => {
  return arr.reduce((acc, val, ind) => {
    return ind >= index ? acc + val : acc;
  }, 0);
});

console.log(partSum); // [41, 31, 26, 20, 8, 1]

⚠️ **O(n²)** - প্রতিটি ইন্ডেক্সের জন্য পুরো অ্যারে ট্রাভার্স করে। বড় অ্যারে জন্য উপযোগী নয়।

পদ্ধতি ২: ডাবল রিকারসন (শিক্ষামূলক)

const arr = [10, 5, 6, 12, 7, 1];

const sumRecursively = (arr, start = 0, res = 0) => {
  if (start < arr.length) {
    return sumRecursively(arr, start + 1, res + arr[start]);
  }
  return res;
};

const partSumRecursively = (arr, partSum = [], start = 0, end = arr.length - 1) => {
  if (start <= end) {
    return partSumRecursively(
      arr, 
      partSum.concat(sumRecursively(arr, start)), 
      ++start, 
      end
    );
  }
  return partSum;
};

console.log(partSumRecursively(arr)); // [41, 31, 26, 20, 8, 1]

পদ্ধতি ৩: ইটারেটিভ O(n) - প্রস্তাবিত (সর্বোত্তম)

const prefixSums = (arr) => {
  const result = [];
  let sum = 0;
  // ডান থেকে বামে ট্রাভার্স করুন
  for (let i = arr.length - 1; i >= 0; i--) {
    sum += arr[i];
    result.unshift(sum); // শুরুতে যোগ করুন
  }
  return result;
};

// অথবা বাম থেকে ডানে (Suffix Sums)
const suffixSums = (arr) => {
  const result = [];
  let sum = 0;
  for (const val of arr) {
    sum += val;
    result.push(sum);
  }
  return result;
};

console.log(prefixSums(arr));  // [41, 31, 26, 20, 8, 1] (Right to Left)
console.log(suffixSums(arr));  // [10, 15, 21, 33, 40, 41] (Left to Right)

পদ্ধতি ৪: ReduceRight (ফাংশনাল O(n))

const prefixSums = arr => 
  arr.reduceRight((acc, val) => {
    acc.unshift((acc[0] || 0) + val);
    return acc;
  }, []);

পদ্ধতি ৫: মেমোইজেশন সহ রিকারসিভ (টপ-ডাউন DP)

const prefixSumsMemo = (arr) => {
  const memo = {};
  
  const sumFrom = (i) => {
    if (i >= arr.length) return 0;
    if (memo[i] !== undefined) return memo[i];
    return memo[i] = arr[i] + sumFrom(i + 1);
  };
  
  return arr.map((_, i) => sumFrom(i));
};

টাইম কমপ্লেক্সিটি তুলনা

আউটপুট

[41, 31, 26, 20, 8, 1]

ব্যবহারিক অ্যাপ্লিকেশন

• রেঞ্জ কোয়েরি (Range Sum Query): O(1) রেঞ্জ সম কোয়েরি
• সাবঅ্যারে সম: `prefix[j] - prefix[i-1]` = subarray sum
• ইকুইলিব্রিয়াম ইন্ডেক্স: বাম ও ডান সম থাকা ইন্ডেক্স
• পারalled প্রসেসিং: ওয়ার্ক ডিস্ট্রিবিউশন

সারাংশ

রিকারসিভ পদ্ধতি অ্যালগরিদমিক চিন্তা দেখাতে ভালো, কিন্তু প্রোডাকশনে **রিভার্স লুপ** বা **reduceRight** ব্যবহার করুন। O(n) টাইম, O(n) স্পেস, কোনো স্ট্যাক ওভারফ্লো রিস্ক নেই।