C# Implicit segment tree ( 19 lines ). Add: O(log(MAX)), Count: O(1)
This task could be solved by SegmentTree (Range updates (Lazy Propagation)), if not for the 1 <= left <= right <= 10^9. \nBut we can use Implicit Segment Tree (
This task could be solved by **SegmentTree** ([Range updates (Lazy Propagation)](https://cp-algorithms.com/data_structures/segment_tree.html#range-updates-lazy-propagation)), if not for the `1 <= left <= right <= 10^9`. \nBut we can use **Implicit Segment Tree** (the idea can be found here [Implicit segment tree](https://cp-algorithms.com/data_structures/segment_tree.html#implicit-segment-tree)).\nThis is my implementation specialized for this task, it turned out to be quite short.\n\n```\npublic class CountIntervals \n{\n    private class SegmentTreeNode \n    {\n        private int _begin, _end;\n        private SegmentTreeNode _leftNode = null, _rightNode = null;\n        \n        public int Count { get; private set; }\n        \n        public SegmentTreeNode(int begin, int end) => (_begin, _end) = (begin, end);\n\n        public int Add(int l, int r) \n        {\n            if (l > r || l > _end || r < _begin) return Count;\n            if ((l == _begin && r == _end) || Count == _end - _begin + 1) return Count = _end - _begin + 1;\n            \n            int middle = _begin + (_end - _begin) / 2;\n            \n            _leftNode = _leftNode ?? new SegmentTreeNode(_begin, middle);\n            _rightNode = _rightNode ?? new SegmentTreeNode(middle + 1, _end);\n            \n            return Count = _leftNode.Add(l, Math.Min(middle, r)) + _rightNode.Add(Math.Max(l, middle + 1), r);\n        }\n    }\n    \n    private SegmentTreeNode _root = new(1, 1_000_000_000);\n    \n    public void Add(int left, int right) => _root.Add(left, right);\n    \n    public int Count() => _root.Count;\n}\n```
['Tree']