Function to return the prefix_sum vector
static int [ ] getPrefixSum ( int [ ] arr ) { int n = arr . Length ; int [ ] new_arr = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) new_arr [ i ] = arr [ i ] ; for ( int i = 1 ; i < n ; i ++ ) new_arr [ i ] = new_arr [ i - 1 ] + new_arr [ i ] ; return new_arr ; }