Java BST solution (with pictures)
We need a data structure that will store intervals without storing overlapping ranges. A data structure that comes to mind that is often used to handle interval
We need a data structure that will store intervals without storing overlapping ranges. A data structure that comes to mind that is often used to handle intervals (and ignoring duplicates) is a bst. Instead of inserting numbers, we insert intervals. If an interval is completely to the left of another, it will be in its left subtree and if an interval is completely to the right, it will be in its right subtree. \n\nBut what about intervals that overlap ? \nWe will cut the intervals so that they will not overlap. This not only allows us to compare intervals easily, we also remove overlapping ranges. The picture attached below should give an idea about what im talking about.\n![image](https://assets.leetcode.com/users/images/03fc91f4-5bbf-4a08-a264-9c8acf782fbf_1652586842.3461363.jpeg)\n\nThe code for inserting an interval would look something like this:\n```\nprivate Node insert(Node node, int l, int r) {\n            if(l > r) {\n                return node;\n            }\n\n            if(node == null) {\n                return new Node(l, r);\n            }\n\t\t\t\n            node.left = insert(node.left, l, Math.min(node.l - 1, r));\n            node.right = insert(node.right, Math.max(node.r + 1, l), r);\n\n            update(node);\n            return balance(node);\n        }\n```\nNow that inserting intervals is taken care of , how do we count the sum of the ranges ? this can easily be done by storing the sum of the ranges of the subtree, for every subtree and always maintaining the invariant subtree_sum = cur_range_sum + left_sum + right_sum.\n![image](https://assets.leetcode.com/users/images/c4adb5e7-c7d5-4695-a84c-5f874a97a733_1652587858.1101189.jpeg)\n\n\nfull code: (a bit long and messy):\n```\nclass CountIntervals {\n\n    private static class AVL {\n        private static class Node {\n            int l, r;\n            int subtree_size;\n            int balance_factor;\n            int height;\n            Node left, right;\n            int range_size;\n\n            Node(int l, int r) {\n                this.l = l;\n                this.r = r;\n                subtree_size = r - l + 1;\n                balance_factor = 0;\n                height = 0;\n                left = right = null;\n                range_size = r - l + 1;\n            }\n            \n            @Override\n            public String toString() {\n                return "Node{" +\n                        "l=" + l +\n                        ", r=" + r +\n                        ", subtree_size=" + subtree_size +\n                        "} range_size: " + range_size;\n            }\n        }\n\n        Node root;\n        AVL() {\n            root = null;\n        }\n\n        public void add(int l, int r) {\n            root = insert(root, l, r);\n        }\n\n        public int size() {\n            if(root == null) {\n                return 0;\n            }\n            return root.subtree_size;\n        }\n\n        private Node insert(Node node, int l, int r) {\n            if(l > r) {\n                return node;\n            }\n\n            if(node == null) {\n                return new Node(l, r);\n            }\n\n           \n            node.left = insert(node.left, l, Math.min(node.l - 1, r));\n            node.right = insert(node.right, Math.max(node.r + 1, l), r);\n\n            update(node);\n            return balance(node);\n        }\n\n        private void update(Node node) {\n            int lh = node.left == null ? -1 : node.left.height;\n            int rh = node.right == null ? -1 : node.right.height;\n            node.height = 1 + Math.max(lh, rh);\n            node.balance_factor = rh - lh;\n\n            int ls = node.left == null ? 0 : node.left.subtree_size;\n            int rs = node.right == null ? 0 : node.right.subtree_size;\n            node.subtree_size = node.range_size + ls + rs;\n        }\n\n        private Node balance(Node node) {\n            //left heavy\n            if(node.balance_factor == -2) {\n                //left left\n                if(node.left.balance_factor <= 0) {\n                    return rightRotate(node);\n                }\n                //left right\n                else {\n                    node.left = leftRotate(node.left);\n                    return rightRotate(node);\n                }\n            }\n            //right heavy\n            else if(node.balance_factor == 2) {\n                //right right\n                if(node.right.balance_factor >= 0) {\n                    return leftRotate(node);\n                }\n                //right left\n                else {\n                    node.right = rightRotate(node.right);\n                    return leftRotate(node);\n                }\n            }\n            return node;\n        }\n\n        private Node rightRotate(Node A) {\n            Node B = A.left;\n            A.left = B.right;\n            B.right = A;\n\n            update(A);\n            update(B);\n            return B;\n        }\n\n        private Node leftRotate(Node B) {\n            Node A = B.right;\n            B.right = A.left;\n            A.left = B;\n\n            update(B);\n            update(A);\n            return A;\n        }\n        \n        private void preorder(Node node) {\n            if(node == null) {\n                return;\n            }\n            System.out.println(node);\n            preorder(node.left);\n            preorder(node.right);\n        }\n    }\n    \n    AVL avl;\n    public CountIntervals() {\n        avl = new AVL();\n    }\n    \n    public void add(int left, int right) {\n        avl.add(left, right);\n    }\n    \n    public int count() {\n        return avl.size();\n    }\n}\n```\n\n
[]