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.
Python code Implementation.
Note: Please feel to comment if you find any errors. Also, suggest if I can improvise this code.