# Fenwick tree approach in Java, O(n ln(n))

• First I replace array of values 'input' with array of their order index 'toOrder' to make Fenwick tree efficient
• Then I maintain Fenwick tree to compute number of values in range (0 .. end), excluding end
• In mapOrder function I use 'order' variable to handle duplicates
• In update and sumRange functions I add 1 to input and subtract 1 before accessing array to work around that Fenwick tree is 1-based
``````public class Solution {
public List<Integer> countSmaller(int[] input) {
int[] toOrder = new int[input.length];
int uniqN = mapOrder(input, toOrder);
int[] tree = new int[uniqN];
Integer[] counts = new Integer[input.length];

for (int i = input.length - 1; i >= 0; --i) {
int order = toOrder[i];
counts[i] = sumRange(tree, order);
update(tree, order, +1);
}

return Arrays.asList(counts);
}

public static int mapOrder(int[] input, int[] toOrder) {
if (input.length == 0) return 0;

Integer[] indexes = new Integer[input.length];
for (int i = 0; i < input.length; ++i)
indexes[i] = i;
Arrays.sort(indexes, (i, j) -> input[i] - input[j]);

int prev = input[indexes[0]];
int order = 0;
for (int j : indexes) {
if (prev != input[j]) {
++order;
prev = input[j];
}
toOrder[j] = order;
}
return order + 1;
}

public int sumRange(int[] tree, int end) {
int sum = 0;
for (int i = end; i > 0; i -= i & -i) {
sum += tree[i-1];
}
return sum;
}

public static void update(int[] tree, int i, int delta) {
i += 1;
for (; i <= tree.length; i += i & -i) {
tree[i-1] += delta;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.