Interval Tree Implementation

Interval Tree is a kind of ordered statistics tree data structure. The data stored on each node of the tree are intervals along with statistics data on the subtree rooted on current node. The interval values can be some kind of measurement in time and space. It is regularly used for geometry queries, find the streets intersect a street on a digital map, or detect if viewers watch a whole youtube video. Along with sweep-line algorithm it was used to solve an important problem during the design of Very Large Scale Integration (VLSI) microprocessor.




public class IntervalTree{
     
        public class Node implements Comparable<Node>{
            int max;
            Interval interval;
         
            Node left, right;
            public Node(Interval inter) {
                this.interval = inter;
                this.max = inter.right;
            }
            @Override
            public int compareTo(Node o){
                return this.interval.left - o.interval.left;
            }
         
            public boolean overlap(Interval inter){
                return this.interval.left <= inter.right && this.interval.right >= inter.left;
            }
        }
     
        public class Interval implements Comparable<Interval>{
            int left, right;
            public Interval(int l, int r){
                this.left = l; this.right = r;
            }
            @Override
            public int compareTo(Interval i){
                return this.left - i.left;
            }
         
            public boolean overlap(Interval inter){
                return this.left <= inter.right && this.right >= inter.left;
            }
         
        }
     
        private Node tree;
     
        public IntervalTree(Interval[] pairs){
            treeBuild(pairs);
        }
     
        /*
         * this implementation assuming static input, use array to present the ordered intervals
         * for dynamically input such as add/delete on the fly,
         * we can use balanced interval tree, then in-order travel to process the tree
         * storage O(n)
         * query time O(n)
         * construction: O(nlog(n))
         * insertion: o(n)
         */
        public int totalLength(Interval[] pairs){
            //sort by the left corr
            Arrays.sort(pairs);
            List<Interval> merged = new ArrayList<Interval>();
            merged.add(pairs[0]);
         
            for(int i=1; i<pairs.length; i++){
                int size = merged.size();
                Interval lastInter = merged.get(size-1);
                if(lastInter.overlap(pairs[i])){
                    lastInter.right = Math.max(lastInter.right, pairs[i].right);
                }else{
                    merged.add(pairs[i]);
                }
            }
         
            int sum = 0;
            for(Interval inter : merged){
                sum += inter.right - inter.left;
            }
            return sum;
        }
     
        public Interval findOne(Interval input){
            Node curr = tree;
            while(curr!=null){
                if(curr.overlap(input))
                    return curr.interval;
                else if(curr.left==null)
                    curr = curr.right;
                else if(curr.left.max < input.left)
                    curr = curr.right;
                else
                    curr = curr.left;
            }
         
            return null;
        }
     
        public List<Interval> findAll(Interval input){
            List<Interval> result = new ArrayList<Interval>();
            findAll(tree, input, result);
            return result;
        }
     
        //in-order travel with condition check against curr.max and curr.left
        public void findAll(Node curr, Interval input, List<Interval> result){
            if(curr==null)
                return;
           // input is to the right of all intervals, no match
            if(curr.max<input.left)
              return;

            if(curr.left!=null)
                findAll(curr.left, input, result);
         
            if(curr.overlap(input))
                result.add(curr.interval);    
            //input is to the left of the all intervals on the right subtree.
            if(input.right < curr.interval.left)
                return;
         
            if(curr.right!=null)
                findAll(curr.right, input, result);
         
        }
     
     
     
        //a simple tree build without balanced
        //ideally we should use splay tree, or r-b tree
        private void treeBuild(Interval[] pairs){
            tree = new Node(pairs[0]);        
            for(int i=1; i<pairs.length; i++)
                insert(pairs[i], tree);
        }
     
        private void insert(Interval inter, Node curr){
            curr.max = Math.max(curr.max, inter.right);
            if(inter.left<=curr.interval.left){
                if(curr.left==null){
                    curr.left = new Node(inter);
                }else
                    insert(inter, curr.left);
            }
            else{
                if(curr.right==null){
                    curr.right = new Node(inter);
                }else
                    insert(inter, curr.right);
            }
        }
     
    }

Total length of overlapping intervals

The original question is here: http://stackoverflow.com/questions/14522808/find-the-total-length-of-overlapped-intervals-using-segment-tree

My implementation takes O(n), but if this query is run multiple times and data structure needs to support dynamic insert and delete, O(n) seems not good enough. Is there any O(logN) solution?

public class Interval implements Comparable<Interval>{

int left, right;

public Interval(int l, int r){

this.left = l; this.right = r;

}

@Override

public int compareTo(Interval i){

return this.left - i.left;

}

public boolean overlap(Interval inter){

return this.left <= inter.right && this.right >= inter.left; 

}

}

/*

 * this implementation assuming static input, use array to present the ordered intervals

 * for dynamically input such as add/delete on the fly, 

* we can use balanced interval tree, then in-order travel to process the tree

* storage O(n)

* query time O(n) 

* construction: O(nlog(n))

* insertion: o(n)

*/

public int totalLength(Interval[] pairs){

//sort by the left corr

Arrays.sort(pairs);

List<Interval> merged = new ArrayList<Interval>();

merged.add(pairs[0]);

for(int i=1; i<pairs.length; i++){

int size = merged.size();

Interval lastInter = merged.get(size-1);

if(lastInter.overlap(pairs[i])){

lastInter.right = Math.max(lastInter.right, pairs[i].right);

}else{

merged.add(pairs[i]);

}

}

int sum = 0;

for(Interval inter : merged){

sum += inter.right - inter.left;

}

return sum;

}