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