JavaScript Binary Range Tree? 700-1000ms
Not sure what to call this data structure. It probably exists or I\'m doing some incorrect version of something that exists. I had what I think a Segment Tree m
Not sure what to call this data structure. It probably exists or I\'m doing some incorrect version of something that exists. I had what I think a Segment Tree might be in my head, but you can let me know.\n\nEssentially we can keep a tree of ranges\n- the root will range from 1 to 1_000_000_000\n- if we add an interval and the current node doesn\'t have anything, we\'ll just set its interval\n- if the current node doesn\'t have children, and we add an interval that overlaps with the current interval, we\'ll just expand the current interval\n- if the current node doesn\'t have children, and we add an interval that doesn\'t overlap with the current interval, we\'ll split the interval in half and add left + right children, then distribute the current interval + the new interval in-so-far as it overlaps with each child\n- if the current node has children, we\'ll add the interval to each child if it overlaps with them\n\n\n```\n\nvar CountIntervals = function() {\n  this.root = new TreeNode(1, 10 ** 9);\n};\n\n/** \n * @param {number} left \n * @param {number} right\n * @return {void}\n */\nCountIntervals.prototype.add = function(left, right) {\n  this.root.addInterval(left, right);\n};\n\n/**\n * @return {number}\n */\nCountIntervals.prototype.count = function() {\n  return this.root.total;\n};\n\n/** \n * Your CountIntervals object will be instantiated and called as such:\n * var obj = new CountIntervals()\n * obj.add(left,right)\n * var param_2 = obj.count()\n */\n\nclass TreeNode {\n  constructor(min, max) {\n    this.min = min;\n    this.max = max;\n    this.currentMin = -1;\n    this.currentMax = -1;\n    this.total = 0;\n    this.left = null;\n    this.right = null;\n  }\n  \n  addInterval(left, right) {\n    // no interval has been set, so just add it\n    if (this.currentMin < 0) {\n      this.currentMin = left;\n      this.currentMax = right;\n      this.total = right - left + 1;\n      return this.total;\n    }\n    \n    const mid = this.min + this.max >> 1;\n    \n\t// we have children, so just add the interval to the children if it overlaps\n    if (this.left) {\n      if (left <= mid) this.left.addInterval(left, Math.min(mid, right));\n      if (right > mid) this.right.addInterval(Math.max(mid + 1, left), right);\n      \n      this.total = this.left.total + this.right.total;\n      return;\n    }\n    \n\t// we don\'t have children\n\t// update the current interval if the new one overlaps with it\n    if (left <= this.currentMax + 1 && right >= this.currentMin - 1) {\n      this.currentMin = Math.min(this.currentMin, left);\n      this.currentMax = Math.max(this.currentMax, right);\n      this.total = this.currentMax - this.currentMin + 1;\n      return;\n    }\n    \n\t// the interval doesn\'t overlap and we don\'t have children\n\t// create left + right children and split our current interval amongst them\n\t// along with adding the new interval to the children if it overlaps\n    this.left = new TreeNode(this.min, mid);\n    this.right = new TreeNode(mid + 1, this.max);\n    \n    if (left <= mid) this.left.addInterval(left, Math.min(mid, right));\n    if (right > mid) this.right.addInterval(Math.max(left, mid + 1), right);\n    if (this.currentMin <= mid) this.left.addInterval(this.currentMin, Math.min(mid, this.currentMax));\n    if (this.currentMax > mid) this.right.addInterval(Math.max(mid + 1, this.currentMin), this.currentMax);\n    \n    this.total = this.left.total + this.right.total;\n  }\n}\n```
['JavaScript']