Shivansh wants to give chapo to Arpit, but only if he is able to solve the following problem.↵
As you are a dear friend of Arpit, you decide to help Arpit solve the problem.↵
Given an array Arr of N numbers. You have to process Q queries on that array. Queries can be of following types :↵
↵
(1)add x to index y↵
(2) given y compute sum of (Arr[i]*(y%i)) for i from 1 to N.↵
↵
Input↵
↵
First Line of input contains two space separated integers N and Q.↵
Second Line contains N space separated integers Arr[1] Arr[2] ..... Arr[N]↵
Next Q lines describe one query each and can be one of the two type:↵
↵
-> 1 i X — Add X to index i.↵
-> 2 Y — compute sum of (Arr[i]*(Y%i)) for i from 1 to N.↵
↵
Constraints↵
↵
1 <= N,Q <= 100000↵
1 <= Arr[i], X, Y <= 100000↵
1 <= i <= N↵
↵
Output↵
↵
For each second type query output one integer per line — answer for this query.↵
↵
Sample input ↵
↵
4 3↵
↵
3 2 3 4↵
↵
1 2 1↵
↵
2 10↵
↵
2 12↵
↵
↵
Sample output ↵
11↵
11↵
↵
0↵
↵
I think it can be solved by segment tree, but I'm not able to figure out how to handle 'y' ?
As you are a dear friend of Arpit, you decide to help Arpit solve the problem.↵
Given an array Arr of N numbers. You have to process Q queries on that array. Queries can be of following types :↵
↵
(1)add x to index y↵
(2) given y compute sum of (Arr[i]*(y%i)) for i from 1 to N.↵
↵
Input↵
↵
First Line of input contains two space separated integers N and Q.↵
Second Line contains N space separated integers Arr[1] Arr[2] ..... Arr[N]↵
Next Q lines describe one query each and can be one of the two type:↵
↵
-> 1 i X — Add X to index i.↵
-> 2 Y — compute sum of (Arr[i]*(Y%i)) for i from 1 to N.↵
↵
Constraints↵
↵
1 <= N,Q <= 100000↵
1 <= Arr[i], X, Y <= 100000↵
1 <= i <= N↵
↵
Output↵
↵
For each second type query output one integer per line — answer for this query.↵
↵
Sample input ↵
↵
4 3↵
↵
3 2 3 4↵
↵
1 2 1↵
↵
2 10↵
↵
2 12↵
↵
↵
Sample output ↵
11↵
↵
0↵
↵
I think it can be solved by segment tree, but I'm not able to figure out how to handle 'y' ?
