Segment Tree | Range Minimum Query

class RangeMinSegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(4 * this.n).fill(Infinity);
        this.build(arr, 0, 0, this.n - 1);
    }
 
    // A recursive function that constructs the Segment Tree
    build(arr, treeIndex, start, end) {
        if (start === end) {
            this.tree[treeIndex] = arr[start];
            return;
        }
 
        const mid = Math.floor((start + end) / 2);
        this.build(arr, 2 * treeIndex + 1, start, mid);
        this.build(arr, 2 * treeIndex + 2, mid + 1, end);
 
        // Internal node stores the minimum of its children
        this.tree[treeIndex] = Math.min(
            this.tree[2 * treeIndex + 1],
            this.tree[2 * treeIndex + 2]
        );
    }
 
    // Function to get the minimum value in a range [qs, qe]
    queryMin(treeIndex, start, end, qs, qe) {
        // Case 1: If segment of this node is a part of given range
        if (qs <= start && qe >= end) {
            return this.tree[treeIndex];
        }
 
        // Case 2: If segment of this node is completely outside the given range
        if (end < qs || start > qe) {
            return Infinity; // Neutral element for minimum query
        }
 
        // Case 3: If a part of this segment overlaps with the given range
        const mid = Math.floor((start + end) / 2);
        return Math.min(
            this.queryMin(2 * treeIndex + 1, start, mid, qs, qe),
            this.queryMin(2 * treeIndex + 2, mid + 1, end, qs, qe)
        );
    }
 
    // Function to update an element in the array and recompute minimums
    update(treeIndex, start, end, idx, newVal) {
        if (idx < start || idx > end) return;
 
        if (start === end) {
            this.tree[treeIndex] = newVal;
            return;
        }
 
        const mid = Math.floor((start + end) / 2);
        this.update(2 * treeIndex + 1, start, mid, idx, newVal);
        this.update(2 * treeIndex + 2, mid + 1, end, idx, newVal);
 
        this.tree[treeIndex] = Math.min(
            this.tree[2 * treeIndex + 1],
            this.tree[2 * treeIndex + 2]
        );
    }
}
 
// Driver Code
const arr = [2, 5, 1, 4, 9, 3];
const rmqTree = new RangeMinSegmentTree(arr);
 
// Query minimum in range [1, 5] (elements: 5, 1, 4, 9, 3 -> minimum is 1)
console.log("Min in range [1, 5]:", rmqTree.queryMin(0, 0, rmqTree.n - 1, 1, 5));
 
// Update index 2 to value 10 (arr becomes [2, 5, 10, 4, 9, 3])
rmqTree.update(0, 0, rmqTree.n - 1, 2, 10);
 
// Query minimum again in range [1, 5] (elements: 5, 10, 4, 9, 3 -> minimum is 3)
console.log("Min in range [1, 5] after update:", rmqTree.queryMin(0, 0, rmqTree.n - 1, 1, 5));