Segment Tree Query

Analysis: Given the query range and segment tree root, find out the max value of that query interval.

There are five situations that could happen when conduct the segment tree query:

1. The query range completely resides outside the node's range. Need to return a very small value Integer.MIN_VALUE

2. The query range completely resides inside the node's range. The maximum is just node.max, max attribute of the node.

3. The query range resides on the left to the mid, which means the query range only has intersection with the range of node.left.

4. The query range resides on the right to the mid, which means the query range only has intersection with the range of node.right.

5. The query range resides across mid of the node's range.

Use graph to represent all these situations. Star stands for endpoints of node's range. Triangle stands for endpoints of query range.

All we need to do in code is just use recursion to deal with all the situations and return the maximum.

Need to mention that in Situation #5, when we divide query range, need to take use of mid as new endpoints.

public int query(SegmentTreeNode root, int start, int end) {
        // When the query range is outside root's range
        if (end < root.start || start > root.end)
            return Integer.MIN_VALUE;

        // When the range of the node is inside of range of query
        if (root.start >= start && root.end <= end)
            return root.max;

        int mid = (root.start+root.end)/2;

        // When mid is on the left of query range
        // Only need to query left subtree
        if (end <= mid)
            return query(root.left, start, end);
        // When the mid is on the right of query range
        // Only need to query right subtree
        if (start >= mid+1)
            return query(root.right, start, end);
        // When the mid in inside the query range
        // Need to query both subtrees
        return Math.max(query(root.left, start, mid), query(root.right, mid+1, end));
    }

Segment Tree Query II

Analysis: Very similar to previous problem. Need to mention that in this problem the root might be null.

Add a new situation: When the root is null, just return 0

public int query(SegmentTreeNode root, int start, int end) {
        // The query range resides completely outside the root's range
        // Or the root is null
        if (root == null || end < root.start || start > root.end)
            return 0;
        // The root's range resides completely inside the query range
        if (start <= root.start && end >= root.end)
            return root.count;

        int mid = (root.start+root.end)/2;
        // The query range is on the left to the mid
        if (end <= mid)
            return query(root.left, start, end);
        // The query range is on the right to the mid
        if (start >= mid+1)
            return query(root.right, start, end);
        // The query range resides across the mid
        return query(root.left, start, mid)+query(root.right, mid+1, end);
    }