Search a target value in interval tree.

Algorithm:

1. if target point within interval of root -> return

2. if target point lies in left side of interval of root, go to left subtree.

3. else

   1. target <= root.left.endMax, go to left subtree
   2. else go to right subtree.

   public class TreeNode {
   Interval interval;
   TreeNode left;
   TreeNode right;
   int limit;  //right most point covered.
   public TreeNode (Interval interval, int limit) {
    this.interval = interval;
    this.limit = limit;
   }
   public TreeNode insert(TreeNode root, Interval interval) {
    if(root == null) {
        return new TreeNode (interval, interval.end);
    }
    if (interval.start < root.left.interval.start) {
          root.left = insert(root.left, interval);
          root.limit = Math.max(root.limit, interval.end);
    } else {
        root.right= insert(root.right, interval);
        root.limit = Math.max(root.limit, interval.end);
    }
    return root;
   }
   }
   

Range Query - Range maximum\/minimum aggregate query

[3,1,2,8,4,6,7,5]

Given an array, support query like

sum[i,j] = b[j] - b[i]

Precompute subarray sum (0,x) = b[x] Time: O(n) Space: O(n)

update(i, newValue) -> update all b[j] which j >= i.

update :O(n) -> O(log n)

query O(1) -> O(log n)

What is min \/ max value of subarray [i,j]

RMQ