How can I implement a data structure which calculates the number of nested intervals in sub-linear time?
Expanding on Dmitry's comment, you can maintain a balanced tree with the left endpoints of the intervals as the keys, and at each node store a balanced tree with the right endpoints as keys, and at each node of each of those trees store a count of intervals.
This requires $O(n\log n)$ space. Lookups are $O(\log^2 n)$. Insertions are tricky because when rebalancing the outer tree you have to rebuild the inner trees, but I think it can be made amortized polylog(n) if you rebalance sufficiently rarely, using a scapegoat tree for example.
If you know that the endpoints will belong to a set of size $k$, and you don't mind factors of $\log k$ in the insertion and lookup times, then you could use a radix tree for the outer tree and avoid the rebalancing logic.