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


  • 0
    T

    Some comments:

    • 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;
            }
        }
    }
    

Log in to reply
 

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