Segment Tree Implementation

SegmentTree.js

class SegmentTree {
  constructor(arr) {
    this.arr = arr
    this.n = arr.length;
    this.tree = Array(4 * this.n).fill(0);
    this.#build(arr, 0, 0, this.n - 1);
  }

  #build = (arr, node, start, end) => {
    if (start === end) {
      // Leaf node will have a single element
      this.tree[node] = arr[start];
    } else {
      let mid = Math.floor((start + end) / 2);
      this.#build(arr, 2 * node + 1, start, mid);
      this.#build(arr, 2 * node + 2, mid + 1, end);
      // Internal node will have the sum of the two children
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
    }
  }

  update = (index, value) => {
    this.#update(index, value, 0, 0, this.n - 1, this.arr);
  }

  #update = (index, value, node, start, end, arr) => {
    if (start === end) {
      // Leaf node
      arr[index] = value;
      this.tree[node] = value;
    } else {
      let mid = Math.floor((start + end) / 2);
      if (start <= index && index <= mid) {
        this.#update(index, value, 2 * node + 1, start, mid, arr);
      } else {
        this.#update(index, value, 2 * node + 2, mid + 1, end, arr);
      }
      // Update internal node
      this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
    }
  }

  query = (L, R) => {
    return this.#query(L, R, 0, 0, this.n - 1);
  }

  #query = (L, R, node, start, end) => {
    if (R < start || L > end) {
      // Range represented by a node is completely outside the given range
      return 0;
    }
    if (L <= start && end <= R) {
      // Range represented by a node is completely inside the given range
      return this.tree[node];
    }
    // Range represented by a node is partially inside and partially outside the given range
    let mid = Math.floor((start + end) / 2);
    let leftSum = this.#query(L, R, 2 * node + 1, start, mid);
    let rightSum = this.#query(L, R, 2 * node + 2, mid + 1, end);
    return leftSum + rightSum;
  }
}

// Usage
let arr = [1, 3, 5, 7, 9, 11];
let segTree = new SegmentTree(arr);

// Query sum in range [1, 3]
console.log(segTree.query(1, 3)); // Output: 15

// Update value at index 1 to 10
segTree.update(1, 10);

// Query sum in range [1, 3] again
console.log(segTree.query(1, 3)); // Output: 22

//-------------------------------------------------------------------------------------------------

//Version 2

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = Array(2 * this.n).fill(0);
    this.build(arr);
  }

  // Build the segment tree
  build(arr) {
    // Initialize leaves with the array elements
    for (let i = 0; i < this.n; i++) {
      this.tree[this.n + i] = arr[i];
    }
    // Build the tree by calculating parents
    for (let i = this.n - 1; i > 0; --i) {
      this.tree[i] = this.tree[i << 1] + this.tree[i << 1 | 1];
    }
  }

  // Modify the value at position p
  modify(p, value) {
    for (this.tree[p += this.n] = value; p > 1; p >>= 1) {
      this.tree[p >> 1] = this.tree[p] + this.tree[p ^ 1];
    }
  }

  // Query the sum on interval [l, r)
  query(l, r) {
    let res = 0;
    for (l += this.n, r += this.n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += this.tree[l++];
      if (r & 1) res += this.tree[--r];
    }
    return res;
  }
}

// Example usage:
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const segTree = new SegmentTree(arr);

// Query sum in range [1, 4)
console.log(segTree.query(1, 4));  // Output: 15 (3 + 5 + 7)

// Update value at index 1 to 10
segTree.modify(1, 10);

// Query sum in range [1, 4) again
console.log(segTree.query(1, 4));  // Output: 22 (10 + 5 + 7)