accidentallygivenfuck's blog

By accidentallygivenfuck, 4 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]
 
 
 
 

»
4 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).

  • »
    »
    21 month(s) 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?

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 months 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?