Prefix Sum is used to solve problems involving the sum of elements between two indices in an array or operations on subarrays.
Using the prefix sum technique,
- After a one-time preprocessing in O(n) time, each range sum query can be answered in O(1) time.
- Thus, if there are q queries, the overall time complexity becomes O(n + q).
Prefix: In general terms, a prefix of a sequence is a part of the sequence that starts from the first element and extends up to a certain position. For an array, the prefix ending at index i includes all elements from index 0 to i.
Prefix Sum: A prefix sum is the cumulative sum of elements of an array from the beginning up to a given index. It represents the total of all elements from index 0 to i.
How to Compute Sum for a Query?
For a query that asks for the sum of elements in the range [L, R] in an array, the result can be obtained by subtracting the prefix sum at index L − 1 from the prefix sum at index R. If L = 0, then the sum is simply equal to prefix[R].
Using Mathematical Notation:
Let the original array be: arr[] = [a0, a1, a2, ..., an-i].
The prefix sum array is: prefix[i] = a0 + a1 + a2 + ... + ai
So,
- prefix[0] = arr[0]
- prefix[1] = arr[0] + arr[1]
- prefix[2] = arr[0] + arr[1] + arr[2]
- ...
Now if we want to calculate the sum from range l to r, we know
Sum(0, r) = prefix[r] and Sum(0, l − 1) = prefix[l − 1].
So now, Sum(l, r) = prefix[r] − prefix[l − 1], and we can easily calculate this in constant time.
Given an array arr[] of integers and a list of queries queries[][], where each query is in the form [L, R], compute the sum of elements from index L to R (both inclusive) for each query.
Example:
Input: arr[] = [2, 4, 6, 8, 10], queries[][] = [[1, 3], [0, 2]]
Output: [18, 12]
Explanation:
Query [1, 3] → 4 + 6 + 8 = 18
Query [0, 2] → 2 + 4 + 6 = 12Input: arr[] = [5, 1, 3, 2], queries[][] = [[0, 1], [2, 3]]
Output: [6, 5]
Explanation:
Query [0, 1] → 5 + 1 = 6
Query [2, 3] → 3 + 2 = 5
Solution : Array Range Sum Solution
Applications of Prefix Sum
- Equilibrium index of an array: The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.
- Find if there is a subarray with 0 sums: Given an array of positive and negative numbers, find if there is a subarray (of size at least one) with 0 sum.
- Maximum subarray size, such that all subarrays of that size have a sum less than k: Given an array of n positive integers and a positive integer k, the task is to find the maximum subarray size such that all subarrays of that size have the sum of elements less than k.
- Find the prime numbers which can be written as sum of most consecutive primes: Given an array of limits. For every limit, find the prime number which can be written as the sum of the most consecutive primes smaller than or equal to the limit.
- Longest Span with same Sum in two Binary arrays: Given two binary arrays, arr1[] and arr2[] of the same size n. Find the length of the longest common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
- Maximum subarray sum modulo m: Given an array of n elements and an integer m. The task is to find the maximum value of the sum of its subarray modulo m i.e find the sum of each subarray mod m and print the maximum value of this modulo operation.
- Maximum occurred integer in n ranges : Given n ranges of the form L and R, the task is to find the maximum occurring integer in all the ranges. If more than one such integer exits, print the smallest one.
- Minimum cost for acquiring all coins with k extra coins allowed with every coin: You are given a list Subarray Sum Equal to kof N coins of different denominations. you can pay an amount equivalent to any 1 coin and can acquire that coin. In addition, once you have paid for a coin, we can choose at most K more coins and can acquire those for free. The task is to find the minimum amount required to acquire all the N coins for a given value of K.
- Random number generator in arbitrary probability distribution fashion: Given n numbers, each with some frequency of occurrence. Return a random number with a probability proportional to its frequency of occurrence.