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.