#NEWLINE# def countRangeSum( self , nums , lower , upper ) : #NEWLINE# #INDENT# '\n        :type nums: List[int]\n        :type lower: int\n        :type upper: int\n        :rtype: int\n        ' #NEWLINE# def countAndMergeSort( sums , start , end , lower , upper ) : #NEWLINE# #INDENT# if ( ( end - start ) <= 0 ) : #NEWLINE# #INDENT# return 0 #NEWLINE# #UNINDENT# mid = ( start + ( ( end - start ) / 2 ) ) #NEWLINE# count = ( countAndMergeSort ( sums , start , mid , lower , upper ) + countAndMergeSort ( sums , ( mid + 1 ) , end , lower , upper ) ) #NEWLINE# ( j , k , r ) = ( ( mid + 1 ) , ( mid + 1 ) , ( mid + 1 ) ) #NEWLINE# tmp = [ ] #NEWLINE# for i in xrange ( start , ( mid + 1 ) ) : #NEWLINE# #INDENT# while ( ( k <= end ) and ( ( sums [ k ] - sums [ i ] ) < lower ) ) : #NEWLINE# #INDENT# k += 1 #NEWLINE# #UNINDENT# while ( ( j <= end ) and ( ( sums [ j ] - sums [ i ] ) <= upper ) ) : #NEWLINE# #INDENT# j += 1 #NEWLINE# #UNINDENT# count += ( j - k ) #NEWLINE# while ( ( r <= end ) and ( sums [ r ] < sums [ i ] ) ) : #NEWLINE# #INDENT# tmp . append ( sums [ r ] ) #NEWLINE# r += 1 #NEWLINE# #UNINDENT# tmp . append ( sums [ i ] ) #NEWLINE# #UNINDENT# sums [ start : ( start + len ( tmp ) ) ] = tmp #NEWLINE# return count #NEWLINE# #UNINDENT# sums = ( [ 0 ] * ( len ( nums ) + 1 ) ) #NEWLINE# for i in xrange ( len ( nums ) ) : #NEWLINE# #INDENT# sums [ ( i + 1 ) ] = ( sums [ i ] + nums [ i ] ) #NEWLINE# #UNINDENT# return countAndMergeSort ( sums , 0 , ( len ( sums ) - 1 ) , lower , upper )