Array range queries over range queries | Python3 program to perform range queries over range queries . ; For prefix sum array ; This function is used to apply square root decomposition in the record array ; Traversing first block in range ; Traversing completely overlapped blocks in range ; Traversing last block in range ; Function to print the resultant array ; Driver code ; If query is of type 2 then function call to record_func ; If query is of type 1 then simply add 1 to the record array ; Merging the value of the block in the record array ; If query is of type 1 then the array elements are over - written by the record array ; The prefix sum of the array ; Printing the resultant array
import math NEW_LINE max = 10000 NEW_LINE def update ( arr , l ) : NEW_LINE INDENT arr [ l ] += arr [ l - 1 ] NEW_LINE DEDENT def record_func ( block_size , block , record , l , r , value ) : NEW_LINE INDENT while ( l < r and l % block_size != 0 and l != 0 ) : NEW_LINE INDENT record [ l ] += value NEW_LINE l += 1 NEW_LINE DEDENT while ( l + block_size <= r + 1 ) : NEW_LINE INDENT block [ l // block_size ] += value NEW_LINE l += block_size NEW_LINE DEDENT while ( l <= r ) : NEW_LINE INDENT record [ l ] += value NEW_LINE l += 1 NEW_LINE DEDENT DEDENT def print_array ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE m = 5 NEW_LINE arr = [ 0 ] * n NEW_LINE record = [ 0 ] * m NEW_LINE block_size = ( int ) ( math . sqrt ( m ) ) NEW_LINE block = [ 0 ] * max NEW_LINE command = [ [ 1 , 1 , 2 ] , [ 1 , 4 , 5 ] , [ 2 , 1 , 2 ] , [ 2 , 1 , 3 ] , [ 2 , 3 , 4 ] ] NEW_LINE for i in range ( m - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( command [ i ] [ 0 ] == 2 ) : NEW_LINE INDENT x = i // ( block_size ) NEW_LINE record_func ( block_size , block , record , command [ i ] [ 1 ] - 1 , command [ i ] [ 2 ] - 1 , ( block [ x ] + record [ i ] + 1 ) ) NEW_LINE DEDENT else : NEW_LINE INDENT record [ i ] += 1 NEW_LINE DEDENT DEDENT for i in range ( m ) : NEW_LINE INDENT check = ( i // block_size ) NEW_LINE record [ i ] += block [ check ] NEW_LINE DEDENT for i in range ( m ) : NEW_LINE INDENT if ( command [ i ] [ 0 ] == 1 ) : NEW_LINE INDENT arr [ command [ i ] [ 1 ] - 1 ] += record [ i ] NEW_LINE if ( ( command [ i ] [ 2 ] - 1 ) < n - 1 ) : NEW_LINE INDENT arr [ ( command [ i ] [ 2 ] ) ] -= record [ i ] NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT update ( arr , i ) NEW_LINE DEDENT print_array ( arr , n ) NEW_LINE DEDENT