ajraj27's blog

Range Query Update Problem.
By ajraj27, history, 10 months 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 (10)
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ajraj27 (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ajraj27 (previous revision, new revision, compare).

→ Reply
»
10 months 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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its from the contest called "newton challenge" which got ended. Link — https://my.newtonschool.co/course/ldrj7tqzlt/timeline/

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

    Can you please explain now ?

    → Reply
    • »
      »
      »
      10 months 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
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Whats the approach you're taking?

        → Reply
        • »
          »
          »
          »
          »
          10 months 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
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Will segment tree be a feasible option ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 months 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