128. Introducing the Interval Tree data structure

An Interval Tree is a flavor of Binary Search Tree (BST). Its particularity consists of the fact that it holds intervals of values. Beside the interval itself, a Node of an Interval Tree holds the maximum value of the current interval and the maximum value of the subtree rooted with this Node.

In code form, an Interval Tree is shaped as follows:

public class IntervalTree {
  private Node root;
  public static final class Interval {
    private final int min, max;
    public Interval(int min, int max) {
      this.min = min;
      this.max = max;
    }
    ...
  }
  private final class Node {
    private final Interval interval;
    private final Integer maxInterval;
    private Node left;
    private Node right;
    private int size;
    private int maxSubstree;
    Node(Interval interval, Integer maxInterval) {
      this.interval = interval;
      this.maxInterval = maxInterval;
      this.size = 1;
      this.maxSubstree...