I tried to solve this problem but failed. Would anyone please help me to solve this problem
Problem Statement:
Sameen has:
1.An array having N integers
2.Q friends
His friends are curious about the array. So, each of his friends asks Sameen a question about the array. Every question is described by 3 integers: i, j and k. In reply to a question, Sameen has to say the “k alternating sum” of the subarray starting at position i and ending at position j [1 based indexing]
“k alternating sum” of a subarray starting at position i and ending at position j can be calculated in the following way:
Add the first k numbers[starting from position i]
Subtract the second k numbers[starting from position i+k]
Add the third k numbers[starting from position i+2*k]
Subtract the fourth k numbers[starting from position i+3*k]
And so on till adding/subtracting the j-th number…
(j-i+1) will be divisible by k.
[See sample Input/output and explanation section for more details]
Can you help Sameen in answering the questions?
Input:
The first line of input contains two integers N and Q. The next line contains N integers, the numbers in the array. Then each of the following Q lines contains 3 integers i, j & k.
Output:
For each query output an integer in a separate line, the answer for that query. Queries should be answered in the order given in the input.
Constraints:
1 ≤ k ≤ 100000
1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
-1000000000 ≤ Value of a number in the array ≤ 1000000000
(j-i+1) will be divisible by k.
Sample Input:
6 6
4 1 -2 -3 4 5
2 5 2
1 6 1
1 6 3
1 6 6
3 3 1
3 4 1
Sample Output:
-2
3
-3
9
-2
1
Break the problem into two cases: when k > sqrt(n) and when k <= sqrt(n). Deal with them in different ways.
Case 1: For any k > sqrt(N) there will be less than sqrt(N) alternating segment. If you have an array, having cumulative sum, you can get the sum of a contiguous segment in O(1). So you can just loop over the alternating parts and get the sum in O(sqrt(N)) for a single query.
Case 2: Now when k <= sqrt(n), you need to do some preprocessing.
let arr[k][i] be the "k alternating sum" of a subarray which starts at position i and keeps alternating untill it reaches a position x such that if you add another segment of size k then it will go out of the array. [ This array can be computed in O(N) , and as you're doing it for every k < sqrt(n), the total complexity is O(N * sqrt(N))] With the help of this array, you can answer every query having k < sqrt(N) in O(1).
Hope that helps.