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;

}