[Data Structure] Segment 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

• Segment Tree
• Top-Down Recursion
• Top-Down Iteration
• Bottom-Up Iteration

---

Code (Top-Down Recursion):

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> output = new LinkedList<>();
        Map<Integer, Integer> rankMap = getRankMap(nums);        
        SegmentTreeNode tree = buildTree(0, nums.length - 1);
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, 0, rank - 1));
            add(tree, rank, 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 SegmentTreeNode buildTree(int lower, int upper) {
        if (lower > upper) {
            return null;
        } else {
            SegmentTreeNode node = new SegmentTreeNode(lower, upper);
            if (lower < upper) {
                int mid = lower + (upper - lower) / 2;
                node.left = buildTree(lower, mid);
                node.right = buildTree(mid + 1, upper);
            }
            return node;
        }
    }
    
    private int sum(SegmentTreeNode node, int lower, int upper) {
        if (lower > upper) {
            return 0;
        }
        if (node.lower == lower && node.upper == upper) {
            return node.sum;
        }
        int mid = node.lower + (node.upper - node.lower) / 2;
        if (upper <= mid) {
            return sum(node.left, lower, upper);
        } else if (lower > mid) {
            return sum(node.right, lower, upper);
        } else {
            return sum(node.left, lower, mid) + sum(node.right, mid + 1, upper);
        }
    }

    private void add(SegmentTreeNode node, int x, int val) {
        if (node.lower == x && node.upper == x) {
            node.sum += val;
            return;
        }
        int mid = node.lower + (node.upper - node.lower) / 2;
        if (x <= mid) {
            add(node.left, x, val);
        } else {
            add(node.right, x, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }

    private class SegmentTreeNode {
        public int lower;
        public int upper;
        public int sum;
        public SegmentTreeNode left;
        public SegmentTreeNode right;
        public SegmentTreeNode(int lower, int upper) {
            this.lower = lower;
            this.upper = upper;
            this.sum = 0;
        }
    }
}

---

Code (Top-Down Iteration):

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> output = new LinkedList<>();
        Map<Integer, Integer> rankMap = getRankMap(nums);        
        int[] tree = new int[4 * nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, 1, 0, nums.length - 1, 0, rank - 1));
            add(tree, 1, 0, nums.length - 1, rank, 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 node, int lower, int upper, int i, int val) {
        if (lower > upper || i < lower || i > upper) {
            return;
        }
        if (lower == upper) {
            tree[node] += val;
            return;
        }
        int mid = lower + (upper - lower) / 2;
        add(tree, 2 * node, lower, mid, i, val);
        add(tree, 2 * node + 1, mid + 1, upper, i, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    private int sum(int[] tree, int node, int lower, int upper, int i, int j) {
        if (lower > upper || j < lower || i > upper) {
            return 0;
        }
        if (lower >= i && upper <= j) {
            return tree[node];
        }
        int mid = lower + (upper - lower) / 2;
        if (j <= mid) {
            return sum(tree, 2 * node, lower, mid, i, j);
        } else if (i > mid) {
            return sum(tree, 2 * node + 1, mid + 1, upper, i, j);
        } else {
            return sum(tree, 2 * node, lower, mid, i, j) + sum(tree, 2 * node + 1, mid + 1, upper, i, j);
        }
    }
}

---

Code (Bottom-Up Iteration):

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> output = new LinkedList<>();
        Map<Integer, Integer> rankMap = getRankMap(nums);        
        int[] tree = new int[2 * nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int rank = rankMap.get(nums[i]);
            output.addFirst(sum(tree, nums.length, 0, rank - 1));
            add(tree, nums.length, rank, 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 int sum(int[] tree, int n, int i, int j) {
        i += n;
        j += n;
        int output = 0;
        while (i <= j) {
            if (i % 2 == 1) {
                output += tree[i++];
            }
            if (j % 2 == 0) {
                output += tree[j--];
            }
            i /= 2;
            j /= 2;
        }
        return output;
    }

    private void add(int[] tree, int n, int i, int val) {
        i += n;
        tree[i] += val;
        for (i /= 2; i > 0; i /= 2) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }
}

---

References:

• https://codeforces.com/blog/entry/18051?locale=ru
• http://hehejun.blogspot.com/2017/11/leetcode-count-of-smaller-numbers-after.html

[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

[Leetcode] Topological Sort

Doc: https://docs.google.com/document/d/1kfn4MfnLLXVNFfayX6L6sjAsZSuUy6gJoJit3sngG-E/edit#heading=h.787pwa54vn0i


Implementation details:

1. Algorithm: DFS. (Kahn's algorithm needs to write codes find in-degrees of all vertices first. Therefore I don't recommend to implement Kahn's algorithm in a limited time. Besides, DFS could detect the cycle in the middle, not in the end.)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then return
    if n has a temporary mark then stop   (not a DAG)
    mark n temporarily
    for each node m with an edge from n to m do
        visit(m)
    mark n permanently
    add n to head of L

(Copy from Wikipedia.)

2. Don't forget to reverse L for correct order.

3. If you don't want to reverse L, you might do topological sort on transpose graph instead.

Topics on Leetcode

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