Data structure and Algorithm-Prefix Sum Array

Photo by Markus Spiske on Unsplash

We will see the implementation of the prefix Sum Array in python.

Before going to direct implementation, we need to answer some questions.

1 Why you should learn Prefix sum array algorithm?

Because it will help calculate the sum of elements in a range in constant time i.e O(1) time.

The idea is very obvious, lets given an array, its prefix array is of the same size and the ith element of prefix array will the sum of elements from 0th till its ith element.

that is

prefix_array[i]=arr[0]+arr[1]+….+…+….+arr[i]

Python code Implementation.

Note: Please feel to comment if you find any errors. Also, suggest if I can improvise this code.