🗓️ Day 5: Prefix Sum and Difference Arrays

🧠 Concept Deep Dive

Prefix Sum is a simple yet powerful technique used to quickly compute the sum of elements in a subarray.

🔹 Prefix Sum Definition:

Given an array nums, the prefix sum array prefix is defined as:

prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

(We usually add a 0 at the beginning for convenience.)

This helps us compute the sum of any subarray [i, j] in constant time:

sum(i, j) = prefix[j+1] - prefix[i]

🔹 Difference Array Definition:

If you need to perform multiple range updates, a Difference Array lets you update entire subarrays efficiently:

diff[i] += val;
diff[j + 1] -= val;

Later, compute the final result with a prefix sum over the diff array.

📖 Prefix Sum Code Example

const nums = [2, 4, 5, 7];
const prefix: number[] = [0];

for (let i = 0; i < nums.length; i++) {
  prefix.push(prefix[i] + nums[i]);
}

// prefix = [0, 2, 6, 11, 18]
// Sum of elements from index 1 to 3 (4 + 5 + 7)
const sum = prefix[4] - prefix[1];
console.log(sum); // Output: 16

🔹 Visualization

Original:      [ 2,  4,  5,  7 ]
Prefix Sum:    [ 0,  2,  6, 11, 18 ]
                         ^     ^
                       prefix[4] - prefix[1] = 16

🤗 Real-world Use Case: Rain Accumulation Tracker

Imagine you measure rainfall every day and want to calculate how much rain fell between Day 5 and Day 10. Instead of looping each time, prefix sums make it instantaneous!

🚧 Difference Array Code Example (Range Updates)

function applyRangeUpdates(length: number, updates: [number, number, number][]): number[] {
  const diff = new Array(length + 1).fill(0);

  for (const [start, end, val] of updates) {
    diff[start] += val;
    if (end + 1 < diff.length) diff[end + 1] -= val;
  }

  // Now compute the final array using prefix sum
  const result = new Array(length);
  result[0] = diff[0];
  for (let i = 1; i < length; i++) {
    result[i] = result[i - 1] + diff[i];
  }

  return result;
}

// Test
console.log(applyRangeUpdates(5, [ [1, 3, 2], [2, 4, 3] ]));
// Output: [0, 2, 5, 5, 3]

🧩 Use Cases

• Querying sum of subarrays in constant time
• Performing multiple range updates efficiently (instead of updating each index)
• Problems involving cumulative totals, e.g. grades, scores, rainfall, distances

🔮 Big O Recap

🧪 Homework (LeetCode-style)

Problem: Range Sum Query

Function Signature:

function rangeSum(nums: number[], i: number, j: number): number;

Constraints:

• 0 ≤ i ≤ j < nums.length
• 1 ≤ nums.length ≤ 10^4

Example

Input: nums = [1, 3, 5, 7, 9], i = 1, j = 3
Output: 15 // 3 + 5 + 7

🔍 Hint: Precompute the prefix sum.

📆 Summary

• Prefix Sum enables O(1) range sum queries.
• Difference Arrays allow efficient bulk updates over a range.
• Both are foundational tools in algorithmic optimization.

🔬 Coming Up

🔼 Day 5: Binary Search Fundamentals Learn the divide-and-conquer powerhouse technique to search sorted arrays in logarithmic time.