Data structure and Algorithm-Prefix Sum Array

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


Python code Implementation.

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



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store