Блог пользователя accidentallygivenfuck

Автор accidentallygivenfuck, 11 лет назад, По-английски

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]
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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