Queries to calculate sum of array elements present at every Yth index starting from the index X | python program for the above approach ; Function to sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... for all possible values of X and Y , where Y is less than or equal to sqrt ( N ) . ; Iterate over all possible values of X ; Precompute for all possible values of an expression such that y <= sqrt ( N ) ; If i + j less than N ; Update dp [ i ] [ j ] ; Update dp [ i ] [ j ] ; Function to Find the sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... for all queries ; dp [ x ] [ y ] : Stores sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... ; Traverse the query array , Q [ ] [ ] ; If y is less than or equal to sqrt ( N ) ; Stores the sum of arr [ x ] + arr [ x + y ] + arr [ x + 2 * y ] + ... ; Traverse the array , arr [ ] ; Update sum ; Update x ; Driver Code
import math NEW_LINE sz = 20 NEW_LINE sqr = int ( math . sqrt ( sz ) ) + 1 NEW_LINE def precomputeExpressionForAllVal ( arr , N , dp ) : NEW_LINE INDENT for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( 1 , int ( math . sqrt ( N ) ) + 1 ) : NEW_LINE INDENT if ( i + j < N ) : NEW_LINE INDENT dp [ i ] [ j ] = arr [ i ] + dp [ i + j ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = arr [ i ] NEW_LINE DEDENT DEDENT DEDENT DEDENT def querySum ( arr , N , Q , M ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( sz ) ] for x in range ( sqr ) ] NEW_LINE precomputeExpressionForAllVal ( arr , N , dp ) NEW_LINE for i in range ( 0 , M ) : NEW_LINE INDENT x = Q [ i ] [ 0 ] NEW_LINE y = Q [ i ] [ 1 ] NEW_LINE if ( y <= math . sqrt ( N ) ) : NEW_LINE INDENT print ( dp [ x ] [ y ] ) NEW_LINE continue NEW_LINE DEDENT sum = 0 NEW_LINE while ( x < N ) : NEW_LINE INDENT sum += arr [ x ] NEW_LINE x += y NEW_LINE DEDENT print ( sum ) NEW_LINE DEDENT DEDENT arr = [ 1 , 2 , 7 , 5 , 4 ] NEW_LINE Q = [ [ 2 , 1 ] , [ 3 , 2 ] ] NEW_LINE N = len ( arr ) NEW_LINE M = len ( Q [ 0 ] ) NEW_LINE querySum ( arr , N , Q , M ) NEW_LINE