text: Queries to calculate sum of array elements present at every Yth index starting from the index X | C # 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 Math . Sqrt ( N ) . ; Iterate over all possible values of X ; Precompute for all possible values of an expression such that y <= Math . 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 Math . 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
code: using System ; class GFG { static int sz = 20 ; static int sqr = ( int ) ( Math . Sqrt ( sz ) ) + 1 ; static void precomputeExpressionForAllVal ( int [ ] arr , int N , int [ , ] dp ) { for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int j = 1 ; j <= Math . Sqrt ( N ) ; j ++ ) { if ( i + j < N ) { dp [ i , j ] = arr [ i ] + dp [ i + j , j ] ; } else { dp [ i , j ] = arr [ i ] ; } } } } static void querySum ( int [ ] arr , int N , int [ , ] Q , int M ) { int [ , ] dp = new int [ sz , sqr ] ; precomputeExpressionForAllVal ( arr , N , dp ) ; for ( int i = 0 ; i < M ; i ++ ) { int x = Q [ i , 0 ] ; int y = Q [ i , 1 ] ; if ( y <= Math . Sqrt ( N ) ) { Console . Write ( dp [ x , y ] + " ▁ " ) ; continue ; } int sum = 0 ; while ( x < N ) { sum += arr [ x ] ; x += y ; } Console . Write ( sum + " ▁ " ) ; } } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 7 , 5 , 4 } ; int [ , ] Q = { { 2 , 1 } , { 3 , 2 } } ; int N = arr . Length ; int M = Q . GetLength ( 0 ) ; querySum ( arr , N , Q , M ) ; } }