accidentallygivenfuck's blog

Segment tree GCD — Range Update & Range Query
By accidentallygivenfuck, 11 years ago, In English

Today I realized that I cannot implement GCD segment tree with range update & range query, the same way I did for min/max/sum segtree with range update & range query. Now I wonder is it possible to write this kind of segment tree with O(logN) complexity for each operation? Operations:

  • Add some number x to range [l, r]
  • Find GCD of range [l, r]

P.S. not to be confused with:

  • Initialize each number in range [l, r] to x
  • Find GCD of range [l, r]
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
11 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Store two segment trees: one for adding some number to range and taking value of element (usual segment tree with lazy propagation) and one based on differences of adjacent elements. When you add a number to the range, only two values in second segment tree change, so you can easily recalculate values in second tree.

Now use the property that gcd(al, al + 1, ..., ar) = gcd(al, al + 1 - al, al + 2 - al + 1, ..., ar - ar - 1).

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

    I am solving this (https://www.codechef.com/problems/DGCD) question using HLD and I am getting TLE Here's my code (https://ideone.com/aUlGTZ). Can you tell me where I'm going wrong?

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

    Please help me in knowing what two values will change in the second segment tree.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      al - al - 1, ar + 1 - ar will change, if they exist.

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

    So basically what we are doing is that we are doing the change operations on 1st segment tree lazily and then querying the first and last element of the range needed. we use this with the middle values from segment tree of consecutive difference which never changes for the given update property. Very nice approach, building a segment tree that doesn't depend on the update at all!! Can anyone give the link to the mentioned problem?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    Very helpful. Thanks.

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

    You could have thanked him after contest :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Can you Please give me the proof of the above property

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

      $$$gcd(a, b) = gcd(a - b, b)$$$ when $$$a \geq b$$$

      $$$gcd(a, b) = gcd(a, b - a)$$$ when $$$a \leq b$$$

      $$$gcd(a, b, c) = gcd(a, gcd(b, c))$$$

      combining all you can generize for $$$n$$$ numbers cases

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

    Isnt the formula above only worked for sorted array a[] only or I missed something ?

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

Is there any problem about this? I'm looking for a problem about this. Thank You.

→ Reply