统计作战单位数

题解利用了一种改进的方法，通过排序和二进制索引树（Binary Indexed Tree, BIT 或 Fenwick Tree）来高效计算索引间的关系。首先，它通过将rating数组排序并映射每个值到其排序后的索引，便于后续操作。对每个士兵j，计算在其左侧有多少数小于它（lsmall）和大于它（llarge），同时计算在其右侧有多少数小于它（rsmall）和大于它（rlarge）。这些值可以通过BIT高效地计算。根据题目要求，对于每个j，有效的组合为lsmall * rlarge（形成递增序列）和llarge * rsmall（形成递减序列）。这样，对每个j，计算这两种情况的数量并累加得到最终结果。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Definition for a class that solves the soldier rating problem

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        # Helper function to add values to BIT
        def add(index: int, val: int) -> None:
            nonlocal bit
            x = index + 1
            while x <= n:
                bit[x] += val
                x += (-x) & x

        # Helper function to get prefix sum up to index
        def get_sum(index: int) -> int:
            nonlocal bit
            x = index + 1
            ans = 0
            while x:
                ans += bit[x]
                x -= (-x) & x
            return ans

        # Function to get range sum between two indices
        def sum_range(left: int, right: int) -> int:
            return get_sum(right) - get_sum(left - 1)

        # Map each rating to its index after sorting
        s = sorted(rating)
        map = {k: v for v, k in enumerate(s)}
        bit, n = [0] * (len(s) + 1), len(s)
        add(map[rating[0]], 1)
        ans = 0
        # Main logic loop over each soldier
        for i in range(1, n - 1):
            cur = map[rating[i]]
            lsmall = get_sum(cur - 1)
            llarge = i - lsmall
            rsmall = cur - lsmall
            rlarge = n - 1 - i - rsmall
            ans += lsmall * rlarge + llarge * rsmall
            add(cur, 1)
        return ans