Initialize and compute the prefix sum array .
$ prefix_sum = array ( ) ; $ prefix_sum [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) $ prefix_sum [ $ i ] = $ prefix_sum [ $ i - 1 ] + $ arr [ $ i ] ;