[Java] Detailed Explanation - TreeSet -> BIT (Fenwick Tree) - O(NlogN)
Updated: Thanks @nmxm for pointing out: TreeSet has the limitation when calling size() on its portion Set (See comment below). There are still some tree structu
**Updated:** Thanks @nmxm for pointing out: TreeSet has the limitation when calling size() on its portion Set (See comment below). There are still some tree structures to use so that we can make it logN, for example -> [Binary Indexed Tree (Fenwick Tree)](https://en.wikipedia.org/wiki/Fenwick_tree). I keep the original code by using TreeSet, and also updated a new version of code by using BIT.\n\n**Ideal:** For every middle solider, count how many soliders smaller than it on the left (cL), how many soliders larger than it on the right (cR). For this solider as middle one, cL * cR is the result of ascending order. Also, do same thing for the descending order.\n\n**Code:** Iterate all soliders as it is the middle solider. And then, count number of solider smaller than it, and bigger than it from both left and right halves by **Fenwick Tree or TreeSet (*deprecated*).**\n\n#### 1. BIT (Fenwick Tree)\n```java\npublic int numTeams(int[] rating) {\n        \n\tif (rating.length < 3) return 0;\n\n\tint N = rating.length;\n\n\tint[] leftTree = new int[(int) 1e5 + 1];\n\tint[] rightTree = new int[(int) 1e5 + 1];\n\n\tfor (int r : rating) update(rightTree, r, 1);\n\n\tint res = 0;\n\tfor (int r : rating) {\n\t\tupdate(rightTree, r, -1);\n\t\tres += (getPrefixSum(leftTree, r - 1) * getSuffixSum(rightTree, r + 1));  // count increase\n\t\tres += (getSuffixSum(leftTree, r + 1) * getPrefixSum(rightTree, r - 1));  // count decrease\n\t\tupdate(leftTree, r, 1);\n\t}\n\n\treturn res;\n}\n\nprivate void update(int[] BIT, int index, int val) {\n\twhile (index < BIT.length) {\n\t\tBIT[index] += val;\n\t\tindex += index & (-index);\n\t}\n}\n\nprivate int getPrefixSum(int[] BIT, int index) {\n\tint sum = 0;\n\twhile (index > 0) {\n\t\tsum += BIT[index];\n\t\tindex -= index & (-index);\n\t}\n\treturn sum;\n}\n\nprivate int getSuffixSum(int[] BIT, int index) {\n\treturn getPrefixSum(BIT, (int) 1e5) - getPrefixSum(BIT, index - 1);\n}\n```\n#### 2. TreeSet (Deprecated)\n```java\n// TreeSet Solution (Deprecated): Using .size() on One of the Views of the Set is still O(n)\nif (rating.length < 3) return 0;\n        \nint N = rating.length;\n\nTreeSet<Integer> leftSet = new TreeSet<>();\nTreeSet<Integer> rightSet = new TreeSet<>();\n\nfor (int i = N - 1; i >= 0; --i) rightSet.add(rating[i]);\n\nint res = 0;\nfor (int i = 0; i < N; ++i) {\n\tint r = rating[i];\n\t\n\trightSet.remove(r);\n\tres += (leftSet.headSet(r).size() * rightSet.tailSet(r).size());  \t// count increase\n\tres += (leftSet.tailSet(r).size() * rightSet.headSet(r).size());  \t// count decrease\n\tleftSet.add(r);\n}\n\nreturn res;\n```
[]