Micro-Drill #248 — Prefix sum vs sliding window

PREFIX SUM vs SLIDING WINDOW
─────────────────────────────
PREFIX SUM:
  pre = [0] * (n + 1)
  for i in range(n): pre[i+1] = pre[i] + a[i]
  sum(a[l:r]) = pre[r] - pre[l]   # O(1) range sum

  Use when:
  □ Multiple range sum queries
  □ Subarray sum equals k (hash + prefix sum)
  □ Non-contiguous or arbitrary ranges
  □ 2D range sums

SLIDING WINDOW:
  Maintain running sum, add right, remove left

  Use when:
  □ Contiguous subarray of fixed/variable size
  □ "Longest/shortest subarray with property X"
  □ All elements positive (monotonic window behavior)

KEY DIFFERENCE:
  Prefix sum: any range query, even with negatives
  Sliding window: contiguous + positive/monotonic only

  "Subarray sum = k" with negatives → prefix sum + hashmap
  "Subarray sum = k" all positive   → sliding window
  "Max sum of size k"               → sliding window