### Riyuzak251097's blog

By Riyuzak251097, history, 9 months ago, ,

Given an array of n integers (1<=n<=300000, 0<=arr[i]<=100000) and q queries (1<=q<=300000) where each query contains 2 integers l and r (1<=l<=r<=n), tell the gcd of all the elements in range l to r (both inclusive).

I am just not getting an idea on how to link query(l) and query(r) in fenwick tree(BIT)

•
• +1
•

 » 9 months ago, # |   0 Auto comment: topic has been updated by Riyuzak251097 (previous revision, new revision, compare).
 » 9 months ago, # |   0 I think (but I'm not sure) it can't be represented in BIT (Fenwick). But it can as segment tree.
•  » » 9 months ago, # ^ |   0 ya i did implement it using a segment tree, just curious to find if we can do the same with a fenwick tree by using some gcd relation i maybe can't think of
•  » » » 9 months ago, # ^ |   0 I don't think so. Fenwick can't for example give you max and min queries. I don't think it's possible for gcd too.
 » 9 months ago, # | ← Rev. 2 →   0 Fenwick can easily answer queries whose have inverses, for example multiplication -> division, addition -> subtraction, xor -> xor.
•  » » 9 months ago, # ^ |   0 Interesting , this fact really made me clear about when to use a fenwick tree
 » 9 months ago, # |   0 mmm you can build a fenwick tree where in each node x save information of array (x — (x&-x), x] i.e. gcd to left and right, then in each query you only consider segment intersection. (memory complexity O(nlog{n}), query complexity O(log^2{n})) :v ugly solution compared with segment tree, but cool idea.
•  » » 9 months ago, # ^ |   +5 Nice! In fenwick array we can store vectors of suffix gcd of [x-(x-x&-x,x] and we need to answer the queries just to the left as much as you can. Why is the complexity log^2(n)? It is log(n)*gcd. And i believe what with a[i]<=10^5 when we calculate gcd logn times numbers gets smaller and gcd counting terminates faster.
•  » » » 9 months ago, # ^ |   0 I think what calculating gcd many times is as hard as calculating gcd(a,b)=1
•  » » » 9 months ago, # ^ |   0 Hey i didn't get your approach, are you telling that we store the gcd from x — x & (-x) to x at that node and same for right? Can you just elaborate a little about your approach and how would we query?
•  » » » » 9 months ago, # ^ |   0 As we know fenwick tree stores array A with index i storing information for (i-i&-i, i], so if we store auffix gcd, we can jump from (l, r) to (l, r-r&-r), or if l>=r-r&-r we can just get the answer.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Complexity actually is , where С is constraint on numbers in array. The second comes from Euclid's algorithm: you can consider amount of its steps during one query processing and show that it doesn't exceed .
 » 9 months ago, # |   +16 Just sort the query in decreasing L, and it can be done by BIT.
•  » » 9 months ago, # ^ |   0 Oh! Offline solution is best in memory!
•  » » 9 months ago, # ^ |   0 Could you explain your solution in more detail please?
•  » » » 9 months ago, # ^ |   +8 Offline solution is good to change inverse with identity (0 in this case) then in you fenwick update gcd while traverse in order of sort.
 » 9 months ago, # |   0 Gonna ask this question in the Fenwick Tree section of the course???? Just Kidding.