Make prefix sum array
let prefixSum = new Array ( arr . length + 1 ) . fill ( 0 ) ; prefixSum [ 1 ] = arr [ 0 ] ; for ( let i = 1 ; i < prefixSum . length - 1 ; ++ i ) { prefixSum [ i + 1 ] = prefixSum [ i ] + arr [ i ] ; }