ajraj27's blog

Range Query Update Problem.
By ajraj27, history, 5 years ago, In English

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'?

tourist Errichto mango_lassi Radewoosh

  • Vote: I like it
  • -36
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What's the source? We don't want to accidentally help you in the upgoing contest. :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain now ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see only $$$O(q \cdot \sqrt{n \cdot \log(n)})$$$, but with rather low constant factor.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Whats the approach you're taking?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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})$$$.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Will segment tree be a feasible option ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply