Prefix Sums & Binary Search on Answer

  • Prefix sums: range sum in O(1)
  • Prefix + map: count subarrays
  • Difference array: batch range updates
  • Binary search on monotonic answers
1 / 5

Prefix sum

  • pref[i] = sum of nums[0..i-1]
  • sum(l..r) = pref[r+1] - pref[l]
2 / 5

Subarray sum = k

  • Need pref[j] - pref[i] = k
  • Count frequencies of prefix sums
3 / 5

Difference array

  • diff[l] += delta
  • diff[r+1] -= delta
  • Final array = prefix(diff)
4 / 5

Binary search on answer

  • Feasible(mid) monotonic
  • Search min feasible
  • low = max weight, high = sum
5 / 5
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.