Initialize and compute the prefix sum array .
prefix_sum = [ ] NEW_LINE prefix_sum . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix_sum . append ( prefix_sum [ i - 1 ] + arr [ i ] ) NEW_LINE DEDENT