Prefix Sum

https://neetcode.io/courses/advanced-algorithms/4

Contiguous subarray starting from zero index

• similar things like prefix product
• post fix - starting from end 9use i-- loop

Problems:

• Given an array, design a data structure that can query the sum of a subarray of the values. e.g. querySum(left, right)
  • A bootsrap solution will be O(n)
  • prefix sum will make it O(1) but needs extra linear memory
  • can be solved using post fix in the same manner
    

More:

• https://leetcode.com/problems/product-of-the-last-k-numbers
  • Catch - what to do with 0