[Javascript] Simple Segment Tree w/ Explanation
\n\n\n\n// e.g: [1,2,5,7]\n// the length of the segment tree will be the length of the array x2\n\n//                               |leaf nodes\n// segment tree
\n\n\n```\n// e.g: [1,2,5,7]\n// the length of the segment tree will be the length of the array x2\n\n//                               |leaf nodes\n// segment tree array: [*,15,3,12,1,2,5,7]\n//                        sums...|\n\n// the first item will always be empty, the sum of all items is the second item.\n\n// To get child nodes:\n// Left child: idx * 2\n// Right child: idx * 2 + 1\n\n// To get parent node:\n// Math.floor(idx / 2)\n\n// n = nums.length\n\n// NumArray: \n// this.segTree will be an array of size (n * 2)\n// build segTree\n\n// build: T.C - O(n), S.C - O(n * 2)\n// Loop through from n to n * 2, filling second half of segTree with nums\n// Loop through from n - 1 to 1 (pointer = i)\n//   set segTree[i] equal the sum of the two children, segTree[i * 2] + segTree[i * 2 + 1]\n\n// update: T.C - O(log(n)), S.C - O(1)\n// start at leaf node, update segTree[index + n] to val\n// Loop while index > 0\n//   let left and right both be index\n//   (remember left child is always even, right child is always odd)\n//   if index is even, increment right by one \n//   else decrement left by one\n//   update index to be parent, Math.floor(index / 2)\n//   update segTree[index] to segTree[left] + segTree[right]\n\n// sumRange: T.C - O(log(n)), S.C - O(1)\n// Set left to left + n, right to right + n (leaf nodes)\n// Loop while left is smaller than or equal to right\n//  (to get the sum, left must be even and right must be odd)\n//   If left is odd, add segTree[left] to sum, increment left.\n//   If right is even, add segTree[right] to sum, decrement right.\n//   Set left to Math.floor(left / 2)\n//   Set right to Math.floor(right / 2)\n// Return sum\n\n\n// Why the left index must be even & right index must be odd:\n    // when left is odd or right is even, this indicates partial coverage. \n    // in other words, the parent node will be covering a range outside of the range we are looking for.\n    // so, we need to take the partial sum and move the pointers closer so that it has full coverage.\n\n\nvar NumArray = function(nums) {\n  this.n = nums.length;\n  this.segTree = new Array(this.n * 2);\n  this.build(nums);\n};\n\nNumArray.prototype.build = function(nums) {\n  let n = this.n;\n  let j = 0;\n  for (var i = n; i < n * 2; i++) {\n    this.segTree[i] = nums[j];\n    j++;\n  }\n  for (i = n - 1; i > 0; i--) {\n    this.segTree[i] = this.segTree[i * 2] + this.segTree[i * 2 + 1];\n  }\n}\n\nNumArray.prototype.update = function(index, val) {\n  let n = this.n;\n  index += n;\n  this.segTree[index] = val;\n  while (index > 1) {\n    let left = index, right = index;\n    if (index % 2 === 0) {\n      right = index + 1;\n    } else {\n      left = index - 1;\n    }\n    index = Math.floor(index / 2);\n    this.segTree[index] = this.segTree[left] + this.segTree[right];\n  }\n};\n\nNumArray.prototype.sumRange = function(left, right) {\n  let n = this.n;\n  left += n, right += n;\n  let sum = 0;\n  while (left <= right) {\n    if (left % 2 === 1) {\n      sum += this.segTree[left];\n      left++;\n    }\n    if (right % 2 === 0) {\n      sum += this.segTree[right];\n      right--;\n    }\n    left = Math.floor(left / 2);\n    right = Math.floor(right / 2);\n  }   \n  return sum;\n};\n```
['Tree', 'JavaScript']