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]
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).
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?
Please help me in knowing what two values will change in the second segment tree.
al - al - 1, ar + 1 - ar will change, if they exist.
what if they don't exist both of them
Please do not discuss problems until 12:00 UTC.
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?
Very helpful. Thanks.
You could have thanked him after contest :)
Ya
Can you Please give me the proof of the above property
$$$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
Isnt the formula above only worked for sorted array a[] only or I missed something ?
Is there any problem about this? I'm looking for a problem about this. Thank You.
try this: link
Thank You.
This one also.