[Data Structure] Binary Indexed Tree

(Ignore some trivial applications.)

Example #1: [Leetcode] Count of Smaller Numbers After Self (315)

Solution: https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit?usp=sharing

Code:

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] tree = new int[nums.length + 1];
        Map<Integer, Integer> rankMap = getRankMap(nums);
        LinkedList<Integer> output = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, rank));
            add(tree, rank + 1, 1);
        }
        return output;
    }
    
    private Map<Integer, Integer> getRankMap(int[] nums) { 
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            map.put(sorted[i], i);
        }
        return map;
    }
    
    private void add(int[] tree, int x, int val) {
        for (int i = x; i < tree.length; i += lowbit(i)) {
            tree[i] += val;
        }
    }
    
    private int sum(int[] tree, int x) {
        int output = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            output += tree[i];
        }
        return output;
    }
    
    private int lowbit(int x) {
        return x & (-x);
    }
}

Notes:

• Sample input: [5,2,6,1,2,4,2,1]
• Sample output: [6,2,5,0,1,2,1,0]
• rankMap, {1=1, 2=4, 4=5, 5=6, 6=7}, is a kind of a data compression of the input because we only care about the relative partial order of the input.

Example #2: [SPOJ] DQUERY - D-query

Solutions:

• https://www.quora.com/What-is-an-approach-to-solve-the-problem-DQUERY-of-SPOJ-using-BIT-Segment-Tree
• https://stackoverflow.com/questions/18553567/difficulty-in-understanding-the-approach-for-solving-spoj-dquery
• https://blog.csdn.net/riba2534/article/details/81128660

References:

• Problem Set: https://cp-algorithms.com/data_structures/fenwick.html