I'm not sure. In order to have O(logn) find complexity, doesn't disjointset need to keep a depth[] array as well? Always do father[find(node1)] = find(node2) can result in O(n) find complexity.
hao26
@hao26
Posts made by hao26

RE: AC JAVA code, Union Find

RE: Summary of the Divide and Conquer based and Binary Indexed Tree based solutions
I think the use of BIT is unnecessary.
So the idea is to find the elements in the prefix sum array whose values are within a range (BTW, this is "value range query" rather than "index range query", which BIT is designed for). After the prefix sum array is sorted, this can already be done in logn time. The only problem left is that when you query range [lower+sum[i1], upper+sum[i1]] for i2 such that sum[i2]sum[i1] is in [lower,upper], you may get an index i2<i1. So to avoid that, you want to keep the prefix sum array dynamic as well as sorted. i.e. deleting sum[i1] after you query it. This can be done by a balanced tree(TreeSet) easily. Even if you don't like trees, you can still do this deletion on the sorted array without BIT.public class Solution { private class SumWithIdx { public long val; public int idx; public SumWithIdx(long a,int b) { val = a; idx = b; } } private class CompareSum implements Comparator<SumWithIdx> { public int compare(SumWithIdx a,SumWithIdx b) { if(a.val<b.val) return 1; else if(a.val>b.val) return 1; else if(a.idx<b.idx) return 1; else return 1; } } public int countRangeSum(int[] nums, int lower, int upper) { if(nums==null  nums.length==0) return 0; TreeSet<SumWithIdx> prefixSums = new TreeSet<>(new CompareSum()); prefixSums.add(new SumWithIdx(0L,1)); long prefixSumSoFar = 0; int cnt = 0; for(int i=0;i<nums.length;++i) { prefixSumSoFar += nums[i]; SumWithIdx lb = new SumWithIdx(prefixSumSoFarupper,2); SumWithIdx ub = new SumWithIdx(prefixSumSoFarlower,nums.length); Set<SumWithIdx> x = prefixSums.subSet(lb, true, ub, true); cnt += x.size(); prefixSums.add(new SumWithIdx(prefixSumSoFar,i)); } return cnt; } }
I am pasting my implementation here but there is another post using TreeMap (for duplicates) that is actually better than this.