Inversion count in an array

Given an array of integers A.
If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A.
Find the total number of inversions of A modulo (10^9 + 7).



Input Format

The only argument given is the integer array A.
Output Format

Return the number of inversions of A modulo (10^9 + 7).
Constraints

1 <= length of the array <= 100000
1 <= A[i] <= 10^9
For Example

Input 1:
    A = [1, 2, 5, 4, 3]
Output 1:
    3

Input 2:
    A = [5, 17, 100, 11]
Output 2:
    1
思路:

用Binary Indexed Tree来做，BIT可以参照这个帖子。

Solution:

Time: O(nlog(maxElement))
Space: O(maxElement)

public class Solution {
    static class Bit {
        public int[] arr;
       
        public Bit(int n) {
            this.arr = new int[n + 1];
        }
       
        public void update(int index, int v) {
            while (index < this.arr.length) {
                this.arr[index] += v;
                index += index & (-index);
            }
        }
       
        public int getSum(int index) {
            int sum = 0;
            while (index > 0) {
                sum += this.arr[index];
                index -= index & (-index);
            }
            return sum;
        }
    }
   
    public int solve(ArrayList<Integer> A) {
        int n = A.size();
        int max = 0;
        for (int i = 0; i < n; i ++) {
            max = Math.max(max, A.get(i));
        }
        Bit bit = new Bit(max);
        int sum = 0;
        for (int i = n - 1; i >= 0; i --) {
            sum += bit.getSum(A.get(i) - 1);
            bit.update(A.get(i), 1);
            // System.out.println(Arrays.toString(bit.arr));
        }
        return sum % (int) (10e9 + 7);
    }
}