SegmentTree.js

/**
 * Segment Tree
 * concept : [Wikipedia](https://en.wikipedia.org/wiki/Segment_tree)
 * inspired by : https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
 *
 * time complexity
 * - init : O(N)
 * - update : O(log(N))
 * - query : O(log(N))
 *
 * space complexity : O(N)
 */
class SegmentTree {
 size
 tree
 constructor(arr) {
 // we define tree like this
 // tree[1] : root node of tree
 // tree[i] : i'th node
 // tree[i * 2] : i'th left child
 // tree[i * 2 + 1] : i'th right child
 // and we use bit, shift operation for index
 this.size = arr.length
 this.tree = new Array(2 * arr.length)
 this.tree.fill(0)

 this.build(arr)
 }

 // function to build the tree
 build(arr) {
 const { size, tree } = this
 // insert leaf nodes in tree
 // leaf nodes will start from index N
 // in this array and will go up to index (2 * N – 1)
 for (let i = 0; i < size; i++) {
 tree[size + i] = arr[i]
 }

 // build the tree by calculating parents
 // tree's root node will contain all leaf node's sum
 for (let i = size - 1; i > 0; --i) {
 // current node's value is the sum of left child, right child
 tree[i] = tree[i * 2] + tree[i * 2 + 1]
 }
 }

 update(index, value) {
 const { size, tree } = this

 // only update values in the parents of the given node being changed.
 // to get the parent move to parent node (index / 2)

 // set value at position index
 index += size
 // tree[index] is leaf node and index's value of array
 tree[index] = value

 // move upward and update parents
 for (let i = index; i > 1; i >>= 1) {
 // i ^ 1 turns (2 * i) to (2 * i + 1)
 // i ^ 1 is second child
 tree[i >> 1] = tree[i] + tree[i ^ 1]
 }
 }

 // interval [L, R) with left index(L) included and right (R) excluded.
 query(left, right) {
 const { size, tree } = this
 // cause R is excluded, increase right for convenient
 right++
 let res = 0

 // loop to find the sum in the range
 for (left += size, right += size; left < right; left >>= 1, right >>= 1) {
 // L is the left border of an query interval

 // if L is odd it means that it is the right child of its parent and our interval includes only L and not the parent.
 // So we will simply include this node to sum and move to the parent of its next node by doing L = (L + 1) / 2.

 // if L is even it is the left child of its parent
 // and the interval includes its parent also unless the right borders interfere.
 if ((left & 1) > 0) {
 res += tree[left++]
 }

 // same in R (the right border of an query interval)
 if ((right & 1) > 0) {
 res += tree[--right]
 }
 }

 return res
 }
}

export { SegmentTree }