Prefix sum is also known as cumulative sum and is used for finding the sum of elements in a specific range in an array or problems that focus on that.
We can do that by creating a helper array (called prefix sum array) that stores the cumulative sum of elements from the original array. Once this sum is available, then this prefix sums can be used to answer various types of queries related to the array. The prefix sum array is constructed by iterating through the original array and calculating the sum of all elements up to the current position. The value at each index in the prefix sum array represents the sum of all elements before that index in the original array.
The prefix sum technique is particularly useful when dealing with problems that involve querying the sum of a range of elements in an array or when you need to find the number of elements that satisfy certain conditions within a range. By using the prefix sum array, these queries can be answered in constant time, regardless of the size of the array. However, using a helper array does require an O(N) storage.