@rodrigozhou Thanks.
Yes.
Here is my SQRT-Decomposition solution CodeChef: Practical coding for everyone
And here is a solution using BIT CodeChef: Practical coding for everyone
1 Like
Yes. Here is my SQRT-Decomposition solution CodeChef: Practical coding for everyone
And here is a solution using BIT CodeChef: Practical coding for everyone
1 Like
It is failing on a very large test case (n = 10^5)
For the query “63001 54725 59725” while the answer is “63001 11” your code last submission on codechef is giving “63001 22” as answer.
1 Like
@anudeep2011 Thanks. Missing this problem will haunt me and my future generations for eternity.
5 Likes
got AC thnx
Much Simpler Solution 
I went through your code of ANUGCD solution using BIT. I didn’t quite understand your BIT query logic to find the max in a range. How can a BIT be used to perform range maximum query?
Can you please explain?
I understand and agree with your above explanation but I think it is valid only for range sum query and NOT min/max query.
Lets take an example (on an index 1 based BIT) for a range max query problem:
This is my input array of size 4:
index: 1 2 3 4
value: 5 3 1 4
This is the BIT constructed on the above input array which stores the max at each node according to your update function:
index: 1 2 3 4
value: 5 5 1 5
How do I get the range max in the interval, say (2, 4) in this case with the above query algorithm?
Expected answer: 4
So, you’re doing query(v,bit,l=2,r=4).
In the first iteration, n=4-(4&-4)=0. So, n<l. This means the interval [1,4] is not contained in [2,4]. Therefore, I’ll do ret=max(ret,v[4])=4 and r=3.
In the second iteration, n=3-(3&-3)=2 and n>=l. This means the interval [3,3] is contained in [2,4] and I can take the accumulated value in bit[3]. So, ret=max(ret,bit[3])=4 and r=2.
In the third iteration, n=2-(2&-2)=0 and n<l. This case is analogue to the first iteration and I’ll do ret=max(ret,v[2])=4 and r=1.
This finishes the while loop and the answer is ret=4.
1 Like
In fact, I think this works for any function… I don’t see any restriction.
I just noticed that you were doing ret = max(ret, v[r–]) and not ret = max(ret, bit[r–]).
Now that I’ve understood it, I find your approach amazing! I was searching exactly for range min/max query using BIT for some time and I am glad that I came across your solution.
How did you come up with this approach? Have you considered writing an article on this? I doubt that many people know this.
Number of possible prime factors is NlogN. we are building segment tree for every possible prime factor and size of that ST is N . So, Space complexity : O(N^2 logN)
Please correct me if I am wrong.
Actually your solution is O(logN^3 ) per Query.