##
*Approach*

There are nearly 78,000 prime numbers between 1 and 10^6, so in worst case a number in this query range L to R can have maximum of 8 prime numbers as the number of factors. Why 8 see 2*3*5*7*11*13*17*19 > 10^6 .And the root node can have maximum of 78,000 nodes with each prime number in the leaf node merging to form the root node.

Now let us think what we should store in a node of segment tree. We may need the following information:-

1. The element of the array so as to compute their prime factors.

2. Some way to combine the factors of each element as key and their count as value,

suppose we are having 2 elements say 8 and 9 so when we merge these node in the tree, we have got 2 as a factor with count 3 and 3 as a factor with count 2 in the merged node.

We now have count of respective prime factors stored in sorted manner in the merged node. If we iterate through every valid value in range X to Y, we will be iterating over at min(Y-X+1 , number of prime numbers as factors) * log (N), where N is number of elements in array.

This is pretty costly and motivates us to store prefix count of prime factors as well, isn't it?

3. So, now we also have to store prefix sum of prime factors in each node.

So , all in all we have the node structure as following ,

### Node Structure

1 2 3 4 5 | struct node{ int val; vector<pi>M; vector<pi>Prefix; }; |

### Sieve of Eratosthenes

So now lets see how we are going to build the tree and merge the nodes.For that first we need to implement Sieve of Eratosthenes to precompute prime factors in the range 1 to 10^6.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | //sieve of Eratosthenes void Sieve(){ int N = 1e6+1; bool isPrime[N]; fill(isPrime,isPrime+N,true); for(int i=2;i*i<=N;i++){ if(isPrime[i]){ for(int j=i*i;j<=N;j+=i){ isPrime[j] = false; } } } for(int i=2;i<=N;i++){ if(isPrime[i]) Primes.pb(i); } } |

##
*Segment Tree Construction*

Now comes the crucial part of the building the tree. Let's see how we store the leaf nodes in the segment tree. I generally use the iterative implementation from Al.Cash's legendary blog Easy and Efficient Segment Tree.We declare the Segment Tree globally as following:-

1 2 | int SZ = 1e5+1; vector<node>t(2*SZ); |

### Filling the leaf nodes

Now we fill the leaf nodes of the trees , We use the Primes vector from the previous sieve() function. and store the required things in the following manner. This part is self explanatory.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | int main(){ Sieve(); int N; scanf("%d",&N); for(int i=0;i<N;i++){ int element; ini(element); int copy = element; int prefixsum = 0 ; t[N+i].val = element; for(int j=0;;j++){ if(Primes[j] > sqrt(copy)){ break; } int cnt=0; while(element >=1 and element%Primes[j] == 0){ element/=Primes[j]; cnt++; } if(cnt!=0){ prefixsum += cnt; t[N+i].M.pb({Primes[j],cnt}); t[N+i].Prefix.pb({Primes[j],prefixsum}); } } if(element>=2){ t[N+i].M.pb({element,1}); t[N+i].Prefix.pb({element,prefixsum+1}); } } build(N); } |

### Building the tree and merging the nodes

Now, let us see how we build the tree and merge the nodes. For merging the node, I use the idea how we merge in Merge-Sort, so merging the nodes can be done in linear times the number of nodes in each leaf for level just above leaf and at root maximum 78,000 nodes need to be merged.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | void build(int N){ for(int i=N-1; i> 0 ;i--){ node left = t[i<<1]; node right = t[i<<1|1]; t[i].val = left.val + right.val; int n = left.M.size(); int m = right.M.size(); int p=0,q=0; int prefixsum = 0 ; while(p<n and q<m){ if(left.M[p].ff < right.M[q].ff){ t[i].M.pb(left.M[p]); prefixsum += left.M[p].ss; t[i].Prefix.pb({left.M[p].ff , prefixsum}); p++; } else if(left.M[p].ff > right.M[q].ff){ t[i].M.pb(right.M[q]); prefixsum += right.M[q].ss; t[i].Prefix.pb({right.M[q].ff , prefixsum}); q++; } else{ t[i].M.pb({left.M[p].ff,left.M[p].ss+right.M[q].ss}); prefixsum += left.M[p].ss + right.M[q].ss; t[i].Prefix.pb({left.M[p].ff , prefixsum}); p++; q++; } } while(p<n){ prefixsum += left.M[p].ss; t[i].M.pb({left.M[p]}); t[i].Prefix.pb({left.M[p].ff , prefixsum}); p++; } while(q<m){ prefixsum += right.M[q].ss; t[i].M.pb({right.M[q]}); t[i].Prefix.pb({right.M[q].ff , prefixsum}); q++; } } } |

### Querying the Segment Tree

Querying the tree is straight forward, we keep on merging the nodes which are required (merging is clearly explained in the Al.Cash's blog, please refer that). It will explain you why we merge the way we merge.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | int query(int N, int L, int R , int X, int Y){ int ANS = 0; for(L += N , R += N ; L < R ; L >>= 1 , R >>= 1){ if(L&1){ int leftI = Greater_equal(t[L].Prefix , X); int rightI = Lesser_equal(t[L].Prefix , Y); if(leftI != -1 and rightI != -1){ if(leftI-1>=0){ ANS += (t[L].Prefix[rightI].ss - t[L].Prefix[leftI-1].ss); } else{ ANS += (t[L].Prefix[rightI].ss); } } L++; } if(R&1){ --R; int leftI = Greater_equal(t[R].Prefix , X); int rightI = Lesser_equal(t[R].Prefix , Y); if(leftI != -1 and rightI != -1){ if(leftI-1>=0){ ANS += (t[R].Prefix[rightI].ss - t[R].Prefix[leftI-1].ss); } else{ ANS += (t[R].Prefix[rightI].ss); } } } } return ANS; } |

### Custom Utility Functions

Custom utility functions are required in the Query function, because we need to find the prefix sum, for that we need to find the prime factor in the node greater than or equal to X and the prime factor less than or equal to the Y. So I wrote the functions by myself, you can use library functions too, but you need to write custom comparator anyway, so I figured it's better to write on my own.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | int Greater_equal(vector<pi> &a, int B){ int lo = 0; int hi = a.size()-1; int index = -1; while(lo<=hi){ int mid = lo + (hi-lo)/2; if(a[mid].ff < B){ lo = mid + 1; } else{ index = mid; hi = mid -1; } } return index; } int Lesser_equal(vector<pi> &a, int B){ int lo = 0; int hi = a.size()-1; int index = -1; while(lo<=hi){ int mid = lo + (hi-lo)/2; if(a[mid].ff > B){ hi = mid - 1; } else{ index = mid; lo = mid + 1; } } return index; } |

Here is the link to the AC solution check it out Solution.

Please share this blog and comment your feed backs.

Nice explanation!!

ReplyDeletethanks

Deletenice work.. :) and that segment tree blog is awesome.

ReplyDeletethank you , truly it is !

Deletethere is no use of val so we can construct struct without val :)

Deleteyeah sure, but it doesn't hurt, just in case you need it. :)

DeleteSir can we use stl maps instead of vector of pairs. merging of stl maps can be done easily.

ReplyDeleteIf you check my previous submissions, I earlier tried maps and somehow in building trees it takes more than 1 sec to build the tree, due to log(N) complexity for insertion and other overheads, so that gives TLE in one test case in last task. so i guess maps won't work, but you can try to optimize that.

DeleteWhat is the memory complexity of the segment tree?

ReplyDeleteLet's see the memory complexity, at root node we can have maximum 78000 nodes, and below that we will be having 2 * 39,000 , below that 4*19500...and son on till height of tree.

Deleteso N + 2*N/2 + 4*N/4 + .........+ log(78000)*78000/log(78,000) = 78,000*log(78000).

This memory is just for the one vector and we have two of them. Otherwise if we have duplicate copies of factors in leaf node, we can have maximum 8 of them in a node at leaves even in that case we will have same N*log(N) space complexity.

Nice explanation!! but i want to know how u build such a theme for blogspot. it's really nice

ReplyDeleteI have used one of the standard themes for blogspot.

DeleteWow, you're using the compact segment tree from leaves. I like that!

ReplyDeleteThank you !!

DeleteNice One !!!!

ReplyDeleteThank you !!

DeleteHey, I followed the exact same approach but got TLE. All complexities are same.

ReplyDeletehttps://www.codechef.com/viewsolution/14389097

Please check it for me and tell whats wrong. Couldn't figure it out

we resolved it on a chat.

DeleteDoing the same but getting TLE in subtask-3, Please check it out this link - https://www.codechef.com/viewsolution/15155710

ReplyDeleteThanks for the explanation. The official editorial was really frustrating to understand.

ReplyDeletevery nice explanation sir!

ReplyDeleteawesome man

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteYou can make the article awesome by putting snapshots of tree after every function or operation.

ReplyDeleteBy the way good article.