# 7ms Java solution using Binary Indexed Tree

• Before move on to try the solution, I suggest you read about binary indexed tree.

``````public class Solution {

/*
In this solution, we use a binary indexed tree (BIT)
Our assumption is that all elements in nums are positive
*/

static int MAX = 11000; //we set max value that can be store in the tree
int[] tree = new int[MAX];

public List<Integer> countSmaller(int[] nums) {
Integer[] result = new Integer[nums.length];

//make all elements in the array posive while maintaining their order
makePositive(nums);

for(int i=nums.length-1; i>=0; i--){
result[i] = get(nums[i]);
}
return Arrays.asList(result);
}

public void makePositive(int[] nums){
int min = MAX;
for(int i=0; i<nums.length; i++)
min = Math.min(min, nums[i]);
if(min < 0){
min = -min+1;
for(int i=0; i<nums.length; i++)
nums[i] += min;
}
}

public void add(int idx, int val){
while(idx<MAX){
tree[idx] += val;
idx += (idx & (-idx));
}
}

public int get(int idx){
int result = 0;
while(idx>0){
result += tree[idx];
idx &= (idx-1);
}
return result;
}
}
``````