Make prefix sum array
vector < int > prefixSum ( arr . size ( ) ) ; prefixSum [ 1 ] = arr [ 0 ] ; for ( int i = 1 ; i < prefixSum . size ( ) - 1 ; ++ i ) { prefixSum [ i + 1 ] = prefixSum [ i ] + arr [ i ] ; }