Count left & right  less or bigger->Fenwick Tree| Segment Tree||2ms Beats 99.79%
Intuition\n Describe your first thoughts on how to solve this problem. \nConsider the middle element in a 3-elemented valid team. Just consider counting how man
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nConsider the middle element in a 3-elemented valid team. Just consider counting how many bigger, smaller elements on his left & right sides.\n\nAn $O(n^2)$ solution is provided which is easy to implemented.\n\n1st time try to use Fenwick tree (binary indexed tree) to solve, so write it in OOP form.\nRef1: https://cp-algorithms.com/data_structures/fenwick.html\nRef2: https://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a\n\n3rd solution uses segment tree.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The code is a nested for-loop. For each soldiert `i` (1<i<n-1) do the following.\n2. Set arrays `L[2], R[2]` containing the number of the bigger/smaller rating than i on the left & one right.\n3. Use loops to count for `L` & for `R`.\n4. Due to counting principle,`L[0]*R[1] + L[1]*R[0]` is the number of the  valid teams for soldier i in the middle; add it to `cnt`.\n5. `cnt` is the answer\n6. 2nd solution uses BIT; in fact BIT has the efficient method to compute prefix sums which can perform fast. \n7. Segment tree is used as the 3rd approach.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\nFenwick tree: $O(n\\log m)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\nFenwick tree: $O(m)$\n# Code||C++ 21ms Beats 92.20%\n```\nclass Solution {\npublic:\n    static int  numTeams(vector<int>& rating) {\n        const int n = rating.size();\n        int cnt= 0;\n        for (int i= 1; i < n-1; i++) {\n            int L[2]={0}, R[2]={0};\n\n            // Count ratings on the left of i\n            for (int j = 0; j < i; j++) \n                L[rating[j] < rating[i]]++;//rating is unique\n            \n            // Count ratings on the right of i\n            for (int k=i+1; k<n; k++) \n                R[rating[k] < rating[i]]++;\n\n            // number of valid teams\n            cnt += L[0]*R[1] + L[1]*R[0];\n        }\n        return cnt;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ using Fenwick tree||2ms Beats 99.79%\nReplace update by add which is more suitable\n```\nstruct FenwickTree{\n    vector<int> BIT;\n    int n;\n    FenwickTree(int n): n(n), BIT(n){}\n\n    void add(int idx, int x){\n        for (; idx<n; idx=idx|(idx+1))\n            BIT[idx] += x;\n    }\n\n    int sum(int idx){// prefix sum\n        int ans = 0;\n        for (; idx>= 0; idx=(idx&(idx+1))-1)\n            ans+=BIT[idx];\n        return ans;\n    }\n\n    int sum(int l, int r){\n        return sum(r)-sum(l-1);\n    }\n};\n\nclass Solution {\npublic:\n    static int  numTeams(vector<int>& rating) {\n        const int n=rating.size();\n        const int m=*max_element(rating.begin(), rating.end());\n\n        FenwickTree L(m+1), R(m+1);\n\n        for(int x: rating) R.add(x, 1);\n\n        int cnt=0;\n        for(int x: rating){\n            R.add(x, -1);// remove x from L\n\n            int LLess=L.sum(x-1);\n            int RLess=R.sum(x-1);\n            int LBigger=L.sum(x+1, m);\n            int RBigger=R.sum(x+1, m);\n\n            cnt+=LLess*RBigger+LBigger*RLess;\n\n            L.add(x, 1);// add x to L\n        }\n        return cnt;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# C++ using Segment tree||3ms Beats 99.68%\n```\nstruct SegmentTree {\n    int n;\n    vector<int> seg;\n\n    SegmentTree(int n) : n(n), seg(2*n) {}\n\n    void update(int i, int x) {\n        i+=n;\n        seg[i]+= x;  // Increment the value at position i\n        for (i>>= 1; i > 0; i>>= 1)\n            seg[i] = seg[2*i] + seg[2*i+1];\n    }\n\n    int query(int l, int r) {\n        int sum = 0;\n        for (l+=n, r+=n; l <= r; l>>=1, r>>=1) {\n            if (l&1) sum += seg[l++];\n            if (!(r&1)) sum += seg[r--];\n        }\n        return sum;\n    }\n};\n\nclass Solution {\npublic:\n    static int numTeams(vector<int>& rating) {\n        const int n=rating.size();\n        const int m=*max_element(rating.begin(), rating.end());\n\n        SegmentTree L(m+1), R(m+1);\n\n        // Initialize R segment tree with the ratings\n        for (int x : rating) R.update(x, 1);\n\n        int cnt = 0;\n        for (int x : rating) {\n            R.update(x, -1);  // Remove x from R\n\n            int LLess=L.sum(x-1);\n            int RLess=R.sum(x-1);\n            int LBigger=L.sum(x+1, m);\n            int RBigger=R.sum(x+1, m);\n\n            cnt+=LLess*RBigger+LBigger*RLess;\n\n            L.update(x, 1);  // Add x to L\n        }\n        return cnt;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Array', 'Bit Manipulation', 'Binary Indexed Tree', 'Segment Tree', 'Counting', 'Prefix Sum', 'C++']