[C#] Fenwick tree | Explained | Beats 100% of users🔥
\n\n# Intuition\nThe Fenwick tree allows us to calculate and update a sum of consecutive elements of a collection in log(n) time, which is perfect for this prob
![image.png](https://assets.leetcode.com/users/images/c1f557f6-1f4a-48ad-bbaa-57169534ca90_1710874558.9687164.png)\n\n# Intuition\nThe Fenwick tree allows us to calculate and update a sum of consecutive elements of a collection in $$log(n)$$ time, which is perfect for this problem.\n\n# Approach\nIn our case, the elements of arrays for which Fenwick trees are built are the number of occurrences of elements in arrays $$arr1$$ and $$arr2$$ respectively. \nEach unique element of the input array, sorted in non-decreasing order, is uniquely mapped to an index in the array for which the Fenwick trees are built.\nTo find the number of array elements that are strictly greater than some value $$x$$, we need to compute the index $$i$$ for the value $$x$$ and use Fenwick tree to compute the difference between the count of all elements and the sum of all Fenwick\'s array elements from zero up to and including the index $$i$$.\n\n# Complexity\n- Time complexity:\n$$O(n*log(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\npublic class Solution\n{\n    public int[] ResultArray(int[] nums)\n    {\n        var arr1 = new List<int>(nums.Length)\n        {\n            nums[0]\n        };\n\n        var arr2 = new List<int>(nums.Length)\n        {\n            nums[1]\n        };\n\n        var tree1 = new GreaterCountBinaryIndexedTree(nums);\n        var tree2 = new GreaterCountBinaryIndexedTree(tree1);\n\n        tree1.Add(nums[0]);\n        tree2.Add(nums[1]);\n\n        for (var i = 2; i < nums.Length; i++)\n        {\n            var gc1 = tree1.GetGreaterCount(nums[i]);\n            var gc2 = tree2.GetGreaterCount(nums[i]);\n\n            if (gc1 > gc2)\n            {\n                arr1.Add(nums[i]);\n                tree1.Add(nums[i]);\n            }\n            else if (gc1 < gc2)\n            {\n                arr2.Add(nums[i]);\n                tree2.Add(nums[i]);\n            }\n            else\n            {\n                if (arr1.Count > arr2.Count)\n                {\n                    arr2.Add(nums[i]);\n                    tree2.Add(nums[i]);\n                }\n                else\n                {\n                    arr1.Add(nums[i]);\n                    tree1.Add(nums[i]);\n                }\n            }\n        }\n\n        return arr1.Concat(arr2).ToArray();\n    }\n}\n\npublic class GreaterCountBinaryIndexedTree\n{\n    internal readonly Dictionary<int, int> IndexByValue;\n    internal readonly int IndexOfLastElement;\n    internal readonly int[] Tree;\n    internal int TotalCount;\n\n    public GreaterCountBinaryIndexedTree(IEnumerable<int> nums)\n    {\n        IndexByValue = nums\n            .Distinct()\n            .OrderBy(n => n)\n            .Select((v, i) => new KeyValuePair<int, int>(v, i))\n            .ToDictionary();\n\n        Tree = new int[IndexByValue.Count];\n        IndexOfLastElement = IndexByValue.Count - 1;\n    }\n\n    public GreaterCountBinaryIndexedTree(GreaterCountBinaryIndexedTree other)\n    {\n        IndexByValue = other.IndexByValue;\n        IndexOfLastElement = other.IndexOfLastElement;\n        Tree = new int[other.Tree.Length];\n    }\n\n    public void Add(int value)\n    {\n        TotalCount++;\n        var index = IndexByValue[value];\n\n        while (index < Tree.Length)\n        {\n            Tree[index]++;\n            index |= index + 1;\n        }\n    }\n\n    public int GetGreaterCount(int value)\n    {\n        var index = IndexByValue[value];\n\n        if (index == IndexOfLastElement)\n        {\n            return 0;\n        }\n\n        return TotalCount - GetLessOrEqualCount(index);\n    }\n\n    private int GetLessOrEqualCount(int index)\n    {\n        var result = 0;\n\n        while (index >= 0)\n        {\n            result += Tree[index];\n\n            if (index is 0)\n            {\n                break;\n            }\n\n            index &= index + 1;\n            index--;\n        }\n\n        return result;\n    }\n}\n```
['Binary Indexed Tree', 'C#']