Arrays: Prefix Sum Technique
Hello there! The prefix sum technique involves creating an array where the prefix[i] is the sum of all elements up to index i. This technique can also be referred to as the cumulative sum, inclusive scan, or simply scan.
prefix[0] = nums[0]
prefix[1] = nums[0] + nums[1]
prefix[2] = nums[0] + nums[1] + nums[2]
prefix[i] = nums[0] + nums[1]+ nums[2] + .. + nums[i]
For example, if the original array is [1, 2, 3, 4], the prefix sum array would be [1, 3, 6, 10].