# BURARRAY - EDITORIAL **URL:** \ **Category:** editorial\ **Tags:** binary-search, editorial, taran\_1407, treap, union-find, ltime73\ **Created:** [June 29, 2019, 2:05am UTC](https://discuss.codechef.com/t/burarray-editorial/29301 "2019-06-29T02:05:59Z")\ **Posts on this page:** 11\ **Page:** 7
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [July 2, 2019, 7:37pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/130 "2019-07-02T19:37:55Z")
Okay glad that you were able to digest it now. ---
**Author:** ![naveen19991124](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naveen19991124/32/24644_2.png) [@naveen19991124](https://discuss.codechef.com/u/naveen19991124)\ **Post date:** [July 3, 2019, 4:55am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/131 "2019-07-03T04:55:20Z")
I have some doubts,please help me out clearing them. 1.How using only path compression as in tester’s solution has time complexity of O(logn) as observed through discussions above. 2.What is (alpha) in Q. 3.According to me time complexity should be O(Q) as in worst case we can perform q updates on consecutive elements and answering range queries. ---
**Author:** ![naveen19991124](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naveen19991124/32/24644_2.png) [@naveen19991124](https://discuss.codechef.com/u/naveen19991124)\ **Post date:** [July 3, 2019, 5:04am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/132 "2019-07-03T05:04:47Z")
@l_returns Can you explain in your solution how do you account for the fact that root having lower rank is made child of root having higher rank in union by rank method.In this method time complexity should be O(logn) as it form balanced trees but if we use only path compression then how time complexity is O(logn) as in tester’s solution. ---
**Author:** ![thefallenstar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/thefallenstar/32/4173_2.png) [@thefallenstar](https://discuss.codechef.com/u/thefallenstar)\ **Post date:** [July 3, 2019, 10:00am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/133 "2019-07-03T10:00:46Z")
This is also solvable using a balanced BST [set] where we insert a pair of elements which represents the range of active elements [\ne 0]. Initially the set it will have only 1 pair : [1, n] and when we delete an element we find the pair on which it lies and delete it. After deletion, insert two more pairs. Like for deletion x, find [l, r] l \le x \le r and then delete this pair. Insert two other pairs : [l, x-1] and [x+1, r] Total operations are no more than 3.Q. Complexity is O(logQ \* Q) ---
**Author:** ![kshitij\_789](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kshitij_789/32/208155_2.png) [@kshitij\_789](https://discuss.codechef.com/u/kshitij_789)\ **Post date:** [July 3, 2019, 10:53am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/134 "2019-07-03T10:53:08Z")
Using path compression complexity is O(Q_alpha(Q)) for processing all queries where alpha is a function which return a number less than 4_Q in CP constraints so yeah linear complexity for path compression ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [July 3, 2019, 1:17pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/135 "2019-07-03T13:17:16Z")
Hey you can’t call it constant. It’s O(Q\*alpha(Q)). You are saying like complexity of BS on q queries is O(q\*\log\_2(n)) and here n=10^5 and hence \log\_2(n)=17 And time complexity is O(q\*17). Which means time complexity of is O(q) 😑😅 Though for our convince we can think as if it’s equivalent to O(Q) as alpha(Q)\<=4 for all practical values of Q. ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [July 3, 2019, 1:24pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/136 "2019-07-03T13:24:45Z")
IDK proof of it. But you can Google about it. “Time complexity of Disjoint set union using path compression” or something similar to it. You will surely find some explaination on why is it’s O(Q\*alpha(Q)) which people often refer as ~ O(Q\*\log\_2(Q)) ---
**Author:** ![hydroman](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hydroman/32/3240_2.png) [@hydroman](https://discuss.codechef.com/u/hydroman)\ **Post date:** [July 3, 2019, 4:02pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/137 "2019-07-03T16:02:10Z")
[https://www.codechef.com/viewsolution/25036895](https://www.codechef.com/viewsolution/25036895) I am getting 80 points. My solution is working for original constraints but surprisingly not working for smaller subtasks. can anybody check my solution? ---
**Author:** ![kshitij\_789](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kshitij_789/32/208155_2.png) [@kshitij\_789](https://discuss.codechef.com/u/kshitij_789)\ **Post date:** [July 4, 2019, 4:35am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/138 "2019-07-04T04:35:08Z")
I know its Q\*alpha(Q) by mistake I left one character.I have edited it now and I had written linear at the last before also. IDK what the confusion is about ---
**Author:** ![pruvi007](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pruvi007/32/2800_2.png) [@pruvi007](https://discuss.codechef.com/u/pruvi007)\ **Post date:** [July 8, 2019, 7:35am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/139 "2019-07-08T07:35:59Z")
Lazy Propagation would help if there would have been range updates. However, here we are only updating 1 index. ---
**Author:** ![pruvi007](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pruvi007/32/2800_2.png) [@pruvi007](https://discuss.codechef.com/u/pruvi007)\ **Post date:** [July 8, 2019, 7:54am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/140 "2019-07-08T07:54:35Z")
I have maintained a map which contains the zeroed out elements. How can we apply binary search in the range to get the max element. ?? [Previous page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=6)