Java BIT/Segment Tree
Intuition\nThis is one of the standard usecase of BIT/Segment Tree, I am using 2 BIT for each arr1 and arr2 (Using lsit l1 and l2)\nAdd 1st element in 1st list,
# Intuition\nThis is one of the standard usecase of BIT/Segment Tree, I am using 2 BIT for each arr1 and arr2 (Using lsit l1 and l2)\nAdd 1st element in 1st list, 2nds in 2nds list add these elemets in there respective BIT.\n\n# Approach\nans nums[i]<=10^9 I am using rank for each number to reduce memory usage lowest element will get highest rank, instead of adding number directly in BIT add its rank, greted element will be of rank r+1 if for number of rank r.\n\n# Complexity\n- Time complexity:\nO(nlongn) for ranking\nO(nlogn) for each BIT operation\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n    class BIT{\n        int bit[], n;\n        BIT(int s){\n            bit = new int[s+1];\n            n = s;\n        }\n        void add(int i, int diff){\n            while(i<=n){\n                bit[i] += diff;\n                i += (i&(-i));\n            }\n        }\n        int query(int i){\n            int sum = 0;\n            while(i>0){\n                sum += bit[i];\n                i -= (i&(-i));\n            }\n            return sum;\n        }\n        int rangeQuery(int l, int r){\n            return query(r)-query(l-1);\n        }\n        \n    }\n    public int[] resultArray(int[] nums) {\n        int i, n = nums.length, sorted[] = new int[n];\n        int r = 1;\n        for(i=0;i<n;i++){\n            sorted[i] = nums[i];\n        }\n        Arrays.sort(sorted);\n        int prev =  -1;\n        Map<Integer, Integer> rank = new HashMap<>();\n        for(i=0;i<n;i++){\n            if(sorted[i]!=prev){\n                rank.put(sorted[i], r++);\n            }\n            prev = sorted[i];\n        }\n        BIT bit1 = new BIT(r), bit2 = new BIT(r);\n        System.out.println(r);\n        List<Integer> l1 = new ArrayList<>(), l2 = new ArrayList<>();\n        l1.add(nums[0]);\n        l2.add(nums[1]);\n        int max = r;\n        r = rank.get(nums[0]);\n        System.out.println(r);\n        bit1.add(r,1);\n        r = rank.get(nums[1]);\n        bit2.add(r,1);\n        for(i=2;i<n;i++){\n            r = rank.get(nums[i]);\n            int g1 = bit1.rangeQuery(r+1, max);\n            int g2 = bit2.rangeQuery(r+1, max);\n            if(g1>g2){\n                l1.add(nums[i]);\n                bit1.add(r,1);\n            }else if(g1<g2){\n                l2.add(nums[i]);\n                bit2.add(r,1);\n            }else if(l1.size()>l2.size()){\n                l2.add(nums[i]);\n                bit2.add(r,1);\n            }else{\n                l1.add(nums[i]);\n                bit1.add(r,1);\n            }\n        }\n        int ans[] = new int[n], j=0;\n        for(i=0;i<l1.size(); i++){\n            ans[j++] = l1.get(i);\n        }\n        for(i=0;i<l2.size(); i++){\n            ans[j++] = l2.get(i);\n        }\n        return ans;\n    }\n}\n```
['Java']