Number of elements less than or equal to a given number in a given subarray | Set 2 ( Including Updates ) | Number of elements less than or equal to a given number in a given subarray and allowing update operations . ; updating the bit array of a valid block ; answering the query ; traversing the first block in range ; Traversing completely overlapped blocks in range for such blocks bit array of that block is queried ; Traversing the last block ; Preprocessing the array ; updating the bit array at the original and new value of array ; Driver Code ; size of block size will be equal to square root of n ; initialising bit array of each block as elements of array cannot exceed 10 ^ 4 so size of bit array is accordingly
MAX = 10001 NEW_LINE def update ( idx , blk , val , bit ) : NEW_LINE INDENT while idx < MAX : NEW_LINE INDENT bit [ blk ] [ idx ] += val NEW_LINE idx += ( idx & - idx ) NEW_LINE DEDENT DEDENT def query ( l , r , k , arr , blk_sz , bit ) : NEW_LINE INDENT summ = 0 NEW_LINE while l < r and l % blk_sz != 0 and l != 0 : NEW_LINE INDENT if arr [ l ] <= k : NEW_LINE INDENT summ += 1 NEW_LINE DEDENT l += 1 NEW_LINE DEDENT while l + blk_sz <= r : NEW_LINE INDENT idx = k NEW_LINE while idx > 0 : NEW_LINE INDENT summ += bit [ l // blk_sz ] [ idx ] NEW_LINE idx -= ( idx & - idx ) NEW_LINE DEDENT l += blk_sz NEW_LINE DEDENT while l <= r : NEW_LINE INDENT if arr [ l ] <= k : NEW_LINE INDENT summ += 1 NEW_LINE DEDENT l += 1 NEW_LINE DEDENT return summ NEW_LINE DEDENT def preprocess ( arr , blk_sz , n , bit ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT update ( arr [ i ] , i // blk_sz , 1 , bit ) NEW_LINE DEDENT DEDENT def preprocessUpdate ( i , v , blk_sz , arr , bit ) : NEW_LINE INDENT update ( arr [ i ] , i // blk_sz , - 1 , bit ) NEW_LINE update ( v , i // blk_sz , 1 , bit ) NEW_LINE arr [ i ] = v NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 5 , 1 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE from math import sqrt NEW_LINE blk_sz = int ( sqrt ( n ) ) NEW_LINE bit = [ [ 0 for i in range ( MAX ) ] for j in range ( blk_sz + 1 ) ] NEW_LINE preprocess ( arr , blk_sz , n , bit ) NEW_LINE print ( query ( 1 , 3 , 1 , arr , blk_sz , bit ) ) NEW_LINE preprocessUpdate ( 3 , 10 , blk_sz , arr , bit ) NEW_LINE print ( query ( 3 , 3 , 4 , arr , blk_sz , bit ) ) NEW_LINE preprocessUpdate ( 2 , 1 , blk_sz , arr , bit ) NEW_LINE preprocessUpdate ( 0 , 2 , blk_sz , arr , bit ) NEW_LINE print ( query ( 0 , 4 , 5 , arr , blk_sz , bit ) ) NEW_LINE DEDENT