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
0
I think it can be solved by segment tree, but I'm not able to figure out how to handle 'y'?
What's the source? We don't want to accidentally help you in the upgoing contest. :)
Can you please explain now ?
I see only $$$O(q \cdot \sqrt{n \cdot \log(n)})$$$, but with rather low constant factor.
Whats the approach you're taking?
Bruteforce small $$$i$$$ for each query and maintain Fenwick tree over possible values of $$$y$$$. When a value of $$$Arr[i]$$$ for big $$$i$$$ changes, then you have to update $$$O(\frac{10^5}{i})$$$ intervals in the Fenwick tree.
For each query, we then bruteforce small $$$i$$$ and read from Fenwick tree for big $$$i$$$. I think that with a sqrt decomposition instead of Fenwick tree we can achieve even $$$O(q \cdot \sqrt{n})$$$.
Will segment tree be a feasible option ?
I'm not sure if $$$O(q \cdot \sqrt{n \cdot \log(n)})$$$ will be enough. If you want to squeeze it, I definitely do not recommend a segment tree.