Java | Fenwick Tree Solution 🔥🔥
Intuition: Fenwick Tree\n Describe your first thoughts on how to solve this problem. \n\n# Complexity\n- Time complexity: O(n.logm)\n Add your time complexity h
# Intuition: Fenwick Tree\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Complexity\n- Time complexity: $$O(n.logm)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] resultArray(int[] nums) {\n        int n = nums.length;\n        \n        // Normalization of input array\n        Map<Integer, Integer> map = new TreeMap<>();\n        for(int i = 0; i < n; i++){\n            map.put(nums[i], 0);\n        }\n        int m = 1;\n        for(Map.Entry<Integer, Integer> it : map.entrySet()){\n            it.setValue(m++);\n        }\n\n        FenwickTree bitA = new FenwickTree(m + 1);\n        FenwickTree bitB = new FenwickTree(m + 1);\n        List<Integer> A = new ArrayList<>();\n        List<Integer> B = new ArrayList<>();        \n\n        for(int i = 0; i < n; i++){\n            int no = map.get(nums[i]);\n            \n            int k = 0;\n            if(i == 0) k = 0;\n            else if(i == 1) k = 1;\n            else {\n                int countA = bitA.range_query(no);\n                int countB = bitB.range_query(no);\n\n                // System.out.println(nums[i] + " " + countA + " " + countB);\n\n                if(countA >= countB){\n                    if(countA == countB && A.size() > B.size()){\n                        k = 1;\n                    }\n                } else {\n                    k = 1;\n                }\n            }\n            \n            if(k == 0){\n                A.add(nums[i]);\n                bitA.update(no, 1);\n                // System.out.println(Arrays.toString(bitA.bit));\n            } else {\n                B.add(nums[i]);\n                bitB.update(no, 1);\n                // System.out.println(Arrays.toString(bitB.bit));\n            }\n        }\n\n        int idx = 0;\n        for(int e : A){\n            nums[idx++] = e;\n        }\n\n        for(int e : B){\n            nums[idx++] = e;\n        }\n\n        return nums;\n    }\n\n    class FenwickTree{\n        int bit[];\n        int n;\n\n        public FenwickTree(int n){\n            this.bit = new int[n];\n            this.n = n;\n        }\n\n        public void update(int idx, int val){\n            while(idx < this.n){\n                this.bit[idx] += val;\n                idx += (idx & -idx);\n            }\n        }\n\n        public int query(int idx){\n            int ans = 0;\n            while(idx > 0){\n                ans += this.bit[idx];\n                idx -= (idx & -idx);\n            }\n            return ans;\n        }\n\n        public int range_query(int no){\n            int for_n = query(n - 1);\n            int for_no = query(no);\n            // System.out.println(for_n + " " + for_no);\n            return for_n - for_no;\n        }\n    }\n}\n```
['Array', 'Binary Indexed Tree', 'Segment Tree', 'Simulation', 'Java']