Introduction to Segment Trees

A Segment Tree is a binary tree used to store intervals or segments. It allows querying which of the stored segments contains a given point, or performing range queries (such as sum, minimum, or maximum) over an array in logarithmic time.

The Problem Scenario

Suppose we have an array arr[0..n-1] and we need to perform two types of operations:

Range Query: Find the sum of elements from index L to R.
Point Update: Change the value of a specified element at index idx to a new value.

Comparison of Approaches:

Naive Array:
- Range Query: O(N) (looping from L to R)
- Point Update: O(1)
Prefix Sum Array:
- Range Query: O(1) (using prefix[R] - prefix[L-1])
- Point Update: O(N) (updating prefix array from idx to n-1)
Segment Tree:
- Range Query: O(log N)
- Point Update: O(log N)

Segment Trees are optimal when there are a large number of both query and update operations.

Structure and Representation

Leaf Nodes represent the individual elements of the input array.
Internal Nodes represent the merged result (e.g., sum, min, or max) of their child nodes.

For an input array of size N, the segment tree is represented as an array of size 4 * N to ensure all nodes fit in the array representation:

Left child of a node at index i is at 2 * i + 1.
Right child of a node at index i is at 2 * i + 2.
Parent of a node at index i is at Math.floor((i - 1) / 2).

JavaScript Implementation (Range Sum Query)

Here is the implementation of a Segment Tree for Range Sum Queries:

class SegmentTree {
    constructor(arr) {
        this.n = arr.length;
        // Allocate memory for the segment tree (4 * N is a safe upper bound)
        this.tree = new Array(4 * this.n).fill(0);
        this.build(arr, 0, 0, this.n - 1);
    }
 
    // A recursive function that constructs the Segment Tree
    build(arr, treeIndex, start, end) {
        // If there is only one element in array, store it in the current node
        if (start === end) {
            this.tree[treeIndex] = arr[start];
            return;
        }
 
        const mid = Math.floor((start + end) / 2);
        // Recursively build left and right subtrees
        this.build(arr, 2 * treeIndex + 1, start, mid);
        this.build(arr, 2 * treeIndex + 2, mid + 1, end);
 
        // Internal node stores sum of left and right children
        this.tree[treeIndex] = this.tree[2 * treeIndex + 1] + this.tree[2 * treeIndex + 2];
    }
 
    // Function to get the sum of elements in a range [qs, qe]
    querySum(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 0;
        }
 
        // Case 3: If a part of this segment overlaps with the given range
        const mid = Math.floor((start + end) / 2);
        return this.querySum(2 * treeIndex + 1, start, mid, qs, qe) +
               this.querySum(2 * treeIndex + 2, mid + 1, end, qs, qe);
    }
 
    // Function to update a value in the input array and segment tree
    updateValue(treeIndex, start, end, idx, diff) {
        // Base Case: If the input index lies outside the range of this segment
        if (idx < start || idx > end) return;
 
        // If the input index is in range of this node, then update the value of the node
        this.tree[treeIndex] += diff;
 
        if (start !== end) {
            const mid = Math.floor((start + end) / 2);
            this.updateValue(2 * treeIndex + 1, start, mid, idx, diff);
            this.updateValue(2 * treeIndex + 2, mid + 1, end, idx, diff);
        }
    }
}
 
// Driver Code
const arr = [1, 3, 5, 7, 9, 11];
const st = new SegmentTree(arr);
 
// Query sum from index 1 to 3 (3 + 5 + 7 = 15)
console.log("Sum in range [1, 3]:", st.querySum(0, 0, st.n - 1, 1, 3)); 
 
// Update index 1 from 3 to 10 (diff = 10 - 3 = 7)
st.updateValue(0, 0, st.n - 1, 1, 7);
 
// Query sum again from index 1 to 3 (10 + 5 + 7 = 22)
console.log("Updated sum in range [1, 3]:", st.querySum(0, 0, st.n - 1, 1, 3));

Complexity Analysis

Time Complexity:
- Construction: O(N) (visits each node in the segment tree once).
- Query: O(log N) (processes at most 4 nodes at each level of the tree).
- Update: O(log N) (propagates changes from leaf to root).
Space Complexity: O(N) to store the segment tree array of size 4 * N.

Count Distinct Rows Range Minimum Query