Create and fill array to store cumulative sum . csum [ i ] stores sum of arr [ 0 ] to arr [ i ]
$ csum = array ( ) ; $ csum [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) $ csum [ $ i ] = $ csum [ $ i - 1 ] + $ arr [ $ i ] ;