C# Dynamic Segment Tree (Implicit Online Search)
\n# Code\n\npublic class CountIntervals {\n    public class Node{\n        public int l, r, add, cnt;\n    }\n    const int N = (int)1e9 + 7, M = 1000010;\n    
\n# Code\n```\npublic class CountIntervals {\n    public class Node{\n        public int l, r, add, cnt;\n    }\n    const int N = (int)1e9 + 7, M = 1000010;\n    Node[] tr = new Node[M * 4];\n    int pos = 1, st = 0;\n\n    public CountIntervals() {\n\n    }\n    \n    public void Add(int left, int right) {\n        st++;\n        Update(1, 1, N - 1, left, right, 1);\n    }\n    \n    public int Count() {\n        if(st == 0) return 0;\n        return Query(1, 1, N - 1, 1, N - 1);\n    }\n\n    public void PushUp(int u){\n        tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;\n    }\n\n    public void PushDown(int u, int len){\n        if(tr[u] == null)\n            tr[u] = new Node();\n        if(tr[u].l == 0){\n            tr[u].l = ++pos;\n            tr[tr[u].l] = new Node();\n        }\n        if(tr[u].r == 0){\n            tr[u].r = ++pos;\n            tr[tr[u].r] = new Node();\n        }\n\n        if(tr[u].add == 0) return;\n        tr[tr[u].l].cnt = len - len / 2;\n        tr[tr[u].r].cnt = len / 2;\n        tr[tr[u].l].add = tr[tr[u].r].add = tr[u].add;\n        tr[u].add = 0;\n    }\n\n    public void Update(int u, int lc, int rc, int l, int r, int k){\n        if(l <= lc && rc <= r){\n            tr[u].add = k;\n            tr[u].cnt = rc - lc + 1;\n            return;\n        }\n\n        PushDown(u, rc - lc + 1);\n        int mid = rc + lc >> 1;\n        if(mid >= l) Update(tr[u].l, lc, mid, l, r, k);\n        if(mid < r) Update(tr[u].r, mid + 1, rc, l, r, k);\n        PushUp(u);\n    }\n\n    public int Query(int u, int lc, int rc, int l, int r){\n        if(l <= lc && rc <= r)\n            return tr[u].cnt;\n        \n        PushDown(u, rc - lc + 1);\n        int mid = lc + rc >> 1, ans = 0;\n        if(l <= mid) ans = Query(tr[u].l, lc, mid, l, r);\n        if(r > mid) ans += Query(tr[u].r, mid + 1, rc, l, r);\n        return ans;\n    }\n}\n\n/**\n * Your CountIntervals object will be instantiated and called as such:\n * CountIntervals obj = new CountIntervals();\n * obj.Add(left,right);\n * int param_2 = obj.Count();\n */\n```
['C#']