### ajraj27's blog

By ajraj27, history, 2 months ago, , 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 :

(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 Arr ..... 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'? Comments (10)
 » Auto comment: topic has been updated by ajraj27 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ajraj27 (previous revision, new revision, compare).
 » What's the source? We don't want to accidentally help you in the upgoing contest. :)
•  » » Its from the contest called "newton challenge" which got ended. Link — https://my.newtonschool.co/course/ldrj7tqzlt/timeline/
•  » » 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})$.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   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.