Prefix array is a very vital tool in competitive programming. This helps to minimize the repeated calculation done in an array and thus reduces the time complexity of your program.

#### What is prefix array ?

Suppose you are given an array, A = { 2 , 6 , 5 , 8 , 7 , 1 }. Let us define a new array PA[ ], size of which is same as the size of array A. The element at the i^{th} index of the array PA will contain the sum of all the elements from A[0] to A[i], i.e :

PA[0] = A[0]

PA[1] = A[0] + A[1]

PA[2] = A[0] + A[1] + A[2]

.

.

.

PA[i] = A[0] + A[1] + A[2] + ........ + A[i]

.

.

.

PA[N-1] = A[0] + A[1] + A[2] + ......... + A[N-1]

So, the prefix array of the given array A will be , PA [ ] = { 2 , 8 , 13 , 21 , 28 , 29 }

#### Creating Prefix array

Prefix array can easily be constructed by travelling the array A once. This can be done by using the formula :

PA[ i ] = PA [ i − 1 ] + A[i]

Here i varies from 1 to N − 1. PA[ 0 ] is initialize to A[ 0 ] before the loop starts.

#### Advantage

Suppose you are said to calculate the sum of first K elements of the array A. It is fine if you have to do the given task once, but if you are asked repeatedly to find the sum of first K elements of the array A (note : K may vary from 0 to N-1 ) then it may take lot of time. But if we construct prefix array of the given array then we can answer the query in O( 1 ) time by just printing PA[ K − 1 ].

Now suppose you are asked to calculate the sum of elements of array A from index L to index R ( L ≤ R) i.e, you have to calculate the summation of the series A[ L ] + A[ L + 1 ] + ........ + A [ R ], if you are asked to calculate once then it is fine but if you have to repeatedly calculate then prefix array would be a better option. We can answer the query in O( 1 ) time by just printing, PA[ R ] − PA[ L − 1 ].

Explanation

PA[ R ] = A[ 0 ] + A [ 1 ] + A[ 2 ] + ....... + A[ L-1 ] + A[ L ] + ........ + A[ R ] (note L ≤ R)

PA[ L-1 ] = A[ 0 ] + A [ 1 ] + A[ 2 ] + ....... + A[ L − 1 ]

substracting PA[ R ] by PA[ L − 1 ] we get:

PA[ R ] − PA[ L − 1] = A[ L ] + ........ + A[ R ]

#### Properties

- If the given array A has all non-negative numbers the the prefix array constructed will be sorted in non-descending order.

Can you suggest some questions on prefix sum?

search usaco guide prefix sums

thanks

Questions on prefix array :- Q1- https://practice.geeksforgeeks.org/problems/longest-subarray-with-sum-divisible-by-k1259/1/?page=1&category[]=prefix-sum&query=page1category[]prefix-sum Q2- https://www.hackerrank.com/contests/ab-yeh-kar-ke-dikhao/challenges/kj-and-street-lights/problem Q3- https://www.hackerearth.com/problem/algorithm/prefix-array-strength/ Q4 — https://www.spoj.com/problems/CSUMQ/

Practice these questions as well:

- Marvolo Gaunt's Ring

[Easy]- Max Chunks To Make Sorted

[Med]- Trapping Rain Water

[Hard]