Fast Range Queries and Point Updates with Segment Trees in JavaScript
In high-frequency data processing applications—such as real-time financial transaction ledgers, analytics dashboards, and telemetry monitoring—systems must repeatedly calculate range aggregates (e.g., sum, minimum, or maximum) over dynamic datasets while values update continuously. A standard array approach requires O(N) time per query, which quickly throttles browser frames or backend event loops as the dataset scales. Conversely, while prefix sum arrays enable lightning-fast O(1) range queries, any point update necessitates recomputing all subsequent prefix entries at an expensive O(N) penalty, rendering them impractical for write-heavy streams.
A Segment Tree resolves this performance bottleneck by organizing interval data into a binary tree structure, achieving an optimal balance with O(log N) complexity for both point updates and arbitrary range queries. By storing the tree inside a flat, compact typed array (where child nodes of index i reside at 2 * i and 2 * i + 1), the data structure avoids object reference overhead and maximizes CPU cache locality. Implementing this classic algorithmic structure in modern JavaScript (ES2023+) gives frontend and Node.js engineers high-throughput streaming aggregations with minimal memory footprint.
Example
// Initializing a segment tree with an array of numbers
const tree = new SegmentTree([1, 3, 5, 7, 9, 11]);
// Query range sum from index 1 to 3 (inclusive: 3 + 5 + 7 = 15) in O(log N)
console.log(tree.queryRange(1, 3)); // 15
// Perform a point update: update index 2 to value 6 in O(log N)
tree.updatePoint(2, 6);
// Query updated range sum (inclusive: 3 + 6 + 7 = 16)
console.log(tree.queryRange(1, 3)); // 16Implementation
/**
* Array-backed Segment Tree for dynamic range sum queries and point updates.
* Provides O(N) initialization and O(log N) point updates and range queries.
*/
class SegmentTree {
/** @type {number} */
#size;
/** @type {Float64Array} */
#tree;
/**
* Constructs the Segment Tree from an initial array of numbers.
* @param {number[]} values
*/
constructor(values) {
if (!Array.isArray(values) || values.length === 0) {
throw new TypeError("SegmentTree requires a non-empty array of numbers.");
}
this.#size = values.length;
// An array of size 4 * N is sufficient to represent a full binary tree for N leaves
this.#tree = new Float64Array(4 * this.#size);
this.#build(values, 1, 0, this.#size - 1);
}
/**
* Recursively constructs the tree nodes.
* @param {number[]} values - The input array
* @param {number} node - Current index in the flat tree array
* @param {number} start - Left boundary of the current segment
* @param {number} end - Right boundary of the current segment
*/
#build(values, node, start, end) {
if (start === end) {
// Leaf node represents a single original element
this.#tree[node] = values[start];
return;
}
const mid = Math.floor((start + end) / 2);
const leftChild = 2 * node;
const rightChild = 2 * node + 1;
// Recursively build children
this.#build(values, leftChild, start, mid);
this.#build(values, rightChild, mid + 1, end);
// Aggregate values (Sum segment tree)
this.#tree[node] = this.#tree[leftChild] + this.#tree[rightChild];
}
/**
* Updates the value at a specific original index in O(log N) time.
* @param {number} index - 0-based index of the element to update
* @param {number} value - New numeric value
*/
updatePoint(index, value) {
if (index < 0 || index >= this.#size) {
throw new RangeError(`Index ${index} is outside bounds [0, ${this.#size - 1}].`);
}
this.#update(1, 0, this.#size - 1, index, value);
}
#update(node, start, end, index, value) {
if (start === end) {
this.#tree[node] = value;
return;
}
const mid = Math.floor((start + end) / 2);
const leftChild = 2 * node;
const rightChild = 2 * node + 1;
if (index <= mid) {
this.#update(leftChild, start, mid, index, value);
} else {
this.#update(rightChild, mid + 1, end, index, value);
}
this.#tree[node] = this.#tree[leftChild] + this.#tree[rightChild];
}
/**
* Computes the sum of elements within [queryLeft, queryRight] inclusive.
* @param {number} queryLeft - 0-based start index
* @param {number} queryRight - 0-based end index
* @returns {number} The aggregated range sum
*/
queryRange(queryLeft, queryRight) {
if (
queryLeft < 0 ||
queryRight >= this.#size ||
queryLeft > queryRight
) {
throw new RangeError("Invalid range parameters.");
}
return this.#query(1, 0, this.#size - 1, queryLeft, queryRight);
}
#query(node, start, end, queryLeft, queryRight) {
// Current segment is completely inside the query range
if (queryLeft <= start && end <= queryRight) {
return this.#tree[node];
}
// Segments are disjoint
if (end < queryLeft || start > queryRight) {
return 0;
}
// Partial overlap: aggregate results from both child subtrees
const mid = Math.floor((start + end) / 2);
const leftChild = 2 * node;
const rightChild = 2 * node + 1;
const leftSum = this.#query(leftChild, start, mid, queryLeft, queryRight);
const rightSum = this.#query(rightChild, mid + 1, end, queryLeft, queryRight);
return leftSum + rightSum;
}
}
// Example usage demonstrating high-throughput interval queries:
const ledger = [120.50, 45.00, 310.25, 89.10, 520.00, 15.75];
const st = new SegmentTree(ledger);
// Query revenue between transactions 1 and 4 inclusive: 45.00 + 310.25 + 89.10 + 520.00 = 964.35
console.log("Range Sum [1, 4]:", st.queryRange(1, 4));
// Ledger correction: transaction 2 was refunded and adjusted to 0
st.updatePoint(2, 0);
// Query updated revenue in logarithmic time: 45.00 + 0 + 89.10 + 520.00 = 654.10
console.log("Updated Range Sum [1, 4]:", st.queryRange(1, 4));Main Point: Segment trees provide logarithmic time complexity for both range queries and point updates by organizing data into an array-backed binary tree.
Credits
Photo by Pawel Czerwinski on Unsplash