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].
Time Complexity
The time complexity of Prefix Sum is O(n) since we need to iterate through the input array once all the items in the array. But after the prefix sum array is computed, we can use it to answer subarray sum queries quickly, in constant time. It allows us to find the sum of any subarray in O(1).
If we want to find the sum of i to j, the answer is prefix[j] - prefix[i] + nums[j];
Problem: Finding subarray sum with Prefix Sum
Given an array nums[] of size N. Given Q queries and in each query given L and R, Print the sum of array elements from index L to R.
Conclusion
The prefix sum technique is a useful algorithmic approach for efficiently computing the cumulative sum of a sequence of numbers. By creating a new sequence that represents the sum of all previous elements in the original sequence up to and including the current element, we can calculate the prefix sum in a single pass through the original list. This technique is particularly useful for applications such as image processing and dynamic programming, where it can significantly improve the efficiency of calculations.