Queries to calculate the Sum of Array elements in the range [ L , R ] having indices as multiple of K | C # program to implement the above approach ; Structure of a Query ; Function to calculate the sum of array elements at indices from range [ L , R ] which are multiples of K for each query ; Stores Prefix Sum ; prefixSum [ i , j ] : Stores the sum from indices [ 0 , j ] which are multiples of i ; If index j is a multiple of i ; Compute prefix sum ; Otherwise ; Traverse each query ; Sum of all indices upto R which are a multiple of K ; Sum of all indices upto L - 1 which are a multiple of K ; Calculate the difference ; Driver Code
using System ; class GFG { class Node { public int L ; public int R ; public int K ; } ; static void kMultipleSum ( int [ ] arr , Node [ ] Query , int N , int Q ) { int [ , ] prefixSum = new int [ N + 1 , N ] ; for ( int i = 1 ; i <= N ; i ++ ) { prefixSum [ i , 0 ] = arr [ 0 ] ; for ( int j = 0 ; j < N ; j ++ ) { if ( j % i == 0 ) { if ( j != 0 ) prefixSum [ i , j ] = arr [ j ] + prefixSum [ i , j - 1 ] ; } else { prefixSum [ i , j ] = prefixSum [ i , j - 1 ] ; } } } for ( int i = 0 ; i < Q ; i ++ ) { int last = prefixSum [ Query [ i ] . K , Query [ i ] . R ] ; int first ; if ( Query [ i ] . L == 0 ) { first = prefixSum [ Query [ i ] . K , Query [ i ] . L ] ; } else { first = prefixSum [ Query [ i ] . K , Query [ i ] . L - 1 ] ; } Console . Write ( last - first + " STRNEWLINE " ) ; } } public static void Main ( String [ ] args ) { int [ ] arr = { 1 , 2 , 3 , 4 , 5 , 6 } ; int N = arr . Length ; int Q = 2 ; Node [ ] Query = new Node [ Q ] ; for ( int i = 0 ; i < Q ; i ++ ) Query [ i ] = new Node ( ) ; Query [ 0 ] . L = 2 ; Query [ 0 ] . R = 5 ; Query [ 0 ] . K = 2 ; Query [ 1 ] . L = 3 ; Query [ 1 ] . R = 5 ; Query [ 1 ] . K = 5 ; kMultipleSum ( arr , Query , N , Q ) ; } }