Actually I am looking for some O(1) for getInterval with O(logN) for add, but it looks not so straight-forward, and perhaps during a 45 minutes interview it will be so hard to code out. Using a set will be much easier to write the code.

```
set<int> tree; // binary search tree implemented by set, ordered
/** Initialize your data structure here. */
SummaryRanges() { }
void addNum(int val) {
tree.insert(val);
}
vector<Interval> getIntervals() {
// this will be about O(N), but very easy to get
vector<Interval> result;
bool isfirst = true;
int begin=0, end=0;
for(int i : tree) {
if(isfirst) {
begin = i;
end = i;
isfirst = false;
}
else {
if( i > end+1) {
result.push_back(Interval(begin, end));
begin = i;
end = i;
}
else {
end = i;
}
}
}
// for last one
result.push_back(Interval(begin, end));
return result;
}
```