Using Segment Tree Patterns
1. Implementing Range Sum Queries
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Build Segment Tree | Constructs the segment tree from an array of elements | O(n) |
O(n) |
| Range Sum Query | Computes the sum of elements in a given range | O(log n) |
O(1) for query, O(n) for construction |
| Update Element | Updates the value of an element in the array | O(log n) |
O(1) for update, O(n) for construction |
Example: Building and Querying a Segment Tree
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
query(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
return this.query(2 * node + 1, start, mid, l, r) +
this.query(2 * node + 2, mid + 1, end, l, r);
}
sumRange(left, right) {
return this.query(0, 0, this.n - 1, left, right);
}
}
// Example usage:
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
console.log(segTree.sumRange(1, 3)); // Output: 15 (3 + 5 + 7)
Note: The segment tree is built as a binary heap where each node stores the sum of its children. For queries, we traverse only the relevant segments to compute the range sum efficiently.
2. Implementing Range Minimum Queries
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Build | Constructs the segment tree from an array of elements | O(n) |
O(n) |
| Query | Find minimum element in a given range [l, r] | O(log n) |
O(1) |
| Update | Update value at a specific index in the array | O(log n) |
O(1) |
Example: Building and Querying a Segment Tree
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = Math.min(this.tree[2 * node + 1], this.tree[2 * node + 2]);
}
}
query(node, start, end, l, r) {
if (r < start || end < l) return Infinity;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
const left = this.query(2 * node + 1, start, mid, l, r);
const right = this.query(2 * node + 2, mid + 1, end, l, r);
return Math.min(left, right);
}
minRange(l, r) {
return this.query(0, 0, this.n - 1, l, r);
}
}
// Example usage:
const arr = [1, 3, 2, 5, 4];
const segTree = new SegmentTree(arr);
console.log(segTree.minRange(1, 3)); // Output: 2
3. Implementing Range Maximum Queries
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| buildTree | Constructs the segment tree from input array | O(n) | O(n) |
| rangeMaxQuery | Queries maximum value in a given range [l, r] | O(log n) | O(1) |
| updateValue | Updates value at a specific index | O(log n) | O(1) |
Example: Range Maximum Query Implementation
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = Math.max(this.tree[2 * node + 1], this.tree[2 * node + 2]);
}
}
query(node, start, end, l, r) {
if (r < start || end < l) return -Infinity;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
const left = this.query(2 * node + 1, start, mid, l, r);
const right = this.query(2 * node + 2, mid + 1, end, l, r);
return Math.max(left, right);
}
rangeMaxQuery(l, r) {
return this.query(0, 0, this.n - 1, l, r);
}
}
// Example usage:
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
console.log(segTree.rangeMaxQuery(1, 4)); // Output: 94. Implementing Point Updates
Segment trees support efficient point updates and range queries. When updating a point in the array, we must propagate changes up the tree to maintain correctness.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| update(index, value) | Updates the value at a specific index in the original array | O(log n) | O(1) |
| buildTree(array) | Initializes the segment tree from an array | O(n) | O(n) |
Example: Point Update Implementation
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
update(node, start, end, index, value) {
if (start === end) {
this.tree[node] = value;
} else {
const mid = Math.floor((start + end) / 2);
if (index <= mid) {
this.update(2 * node + 1, start, mid, index, value);
} else {
this.update(2 * node + 2, mid + 1, end, index, value);
}
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
query(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
return this.query(node * 2 + 1, start, mid, l, r) +
this.query(node * 2 + 2, mid + 1, end, l, r);
}
}
// Usage example:
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
segTree.update(0, 0, arr.length - 1, 1, 10); // Update index 1 to value 10
console.log(segTree.query(0, 0, arr.length - 1, 0, 2)); // Sum from index 0 to 2
Note: The update operation modifies only the necessary nodes in the segment tree to reflect the new value at a specific index. The propagation happens from leaf to root, ensuring that parent nodes correctly represent the sum of their children.
5. Implementing Range Updates
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| updateRange(tree, l, r, value) | Updates all elements in range [l, r] with a given value | O(log n) | O(1) |
| rangeUpdate(tree, l, r, value) | Applies a value to all elements in range [l, r] | O(log n) | O(1) |
Example: Range Update Implementation
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.lazy = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
push(node, start, end) {
if (this.lazy[node] !== 0) {
this.tree[node] += this.lazy[node] * (end - start + 1);
if (start !== end) {
this.lazy[2 * node + 1] += this.lazy[node];
this.lazy[2 * node + 2] += this.lazy[node];
}
this.lazy[node] = 0;
}
}
updateRange(node, start, end, l, r, value) {
this.push(node, start, end);
if (start > r || end < l) return;
if (start >= l && end <= r) {
this.lazy[node] += value;
this.push(node, start, end);
return;
}
const mid = Math.floor((start + end) / 2);
this.updateRange(2 * node + 1, start, mid, l, r, value);
this.updateRange(2 * node + 2, mid + 1, end, l, r, value);
this.push(2 * node + 1, start, mid);
this.push(2 * node + 2, mid + 1, end);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
// Usage example:
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
segTree.updateRange(0, 0, arr.length - 1, 1, 3, 2); // Add 2 to indices 1-3
Note: Lazy propagation is essential for efficient range updates in segment trees to avoid O(n) operations per update.
6. Solving Range GCD Queries
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Build Segment Tree | Constructs a segment tree from an array of integers to support range GCD queries | O(n) |
O(n) |
| Range GCD Query | Computes the GCD of elements in a given range [l, r] | O(log n) |
O(1) (excluding tree storage) |
| Update Element | Updates the value at a specific index in the array | O(log n) |
O(1) (excluding tree storage) |
Example: Building and Querying a Segment Tree for GCD
function buildSegmentTree(arr) {
const n = arr.length;
const tree = new Array(4 * n).fill(0);
function build(node, start, end) {
if (start === end) {
tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = gcd(tree[2 * node], tree[2 * node + 1]);
}
}
build(1, 0, n - 1);
return tree;
}
function query(tree, node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
const mid = Math.floor((start + end) / 2);
const leftGcd = query(tree, 2 * node, start, mid, l, r);
const rightGcd = query(tree, 2 * node + 1, mid + 1, end, l, r);
return gcd(leftGcd, rightGcd);
}
function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
// Example usage:
const arr = [2, 4, 6, 8, 10];
const tree = buildSegmentTree(arr);
console.log(query(tree, 1, 0, arr.length - 1, 1, 3)); // GCD of [4, 6, 8] = 2
Note: The segment tree is built using a binary heap-like structure where each node stores the GCD of its children. The query operation uses a divide-and-conquer approach to efficiently compute the GCD over a range.
7. Implementing Range Assignment
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| rangeAssign(l, r, value) | Assigns a new value to all elements in the range [l, r] | O(log n) | O(n) |
| rangeUpdate(l, r, value) | Updates all elements in the range [l, r] with a new value | O(log n) | O(n) |
Example: Range Assignment Implementation
class SegmentTree {
constructor(size) {
this.size = size;
this.tree = new Array(4 * size).fill(0);
this.lazy = new Array(4 * size).fill(0);
}
pushDown(node, start, end) {
if (this.lazy[node] !== 0 && start !== end) {
this.tree[2 * node] = this.lazy[node];
this.tree[2 * node + 1] = this.lazy[node];
this.lazy[2 * node] = this.lazy[node];
this.lazy[2 * node + 1] = this.lazy[node];
this.lazy[node] = 0;
}
}
rangeAssign(l, r, value, node = 1, start = 0, end = this.size - 1) {
if (l > end || r < start) return;
if (l <= start && end <= r) {
this.tree[node] = value;
this.lazy[node] = value;
return;
}
this.pushDown(node, start, end);
const mid = Math.floor((start + end) / 2);
this.rangeAssign(l, r, value, 2 * node, start, mid);
this.rangeAssign(l, r, value, 2 * node + 1, mid + 1, end);
this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
}
query(l, r, node = 1, start = 0, end = this.size - 1) {
if (l > end || r < start) return 0;
if (l <= start && end <= r) return this.tree[node];
this.pushDown(node, start, end);
const mid = Math.floor((start + end) / 2);
return this.query(l, r, 2 * node, start, mid) +
this.query(l, r, 2 * node + 1, mid + 1, end);
}
}
// Usage example:
const segTree = new SegmentTree(10);
segTree.rangeAssign(2, 5, 100); // Assigns value 100 to indices 2 through 5
console.log(segTree.query(2, 3)); // Outputs 100
Note: Lazy propagation is essential for efficient range assignment operations in segment trees.
8. Solving Count of Elements
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| countInRange | Counts elements in a range [l, r] | O(log n) | O(n) |
| countLessThan | Counts elements less than a value | O(log n) | O(n) |
| countGreaterThan | Counts elements greater than a value | O(log n) | O(n) |
Example: Count Elements in Range
const segmentTree = new SegmentTree([1, 3, 5, 7, 9]);
const count = segmentTree.countInRange(1, 3); // Returns 2 (elements 3 and 5)
Note: The segment tree must be built with the array elements to support range queries.
9. Implementing Historic Queries
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| queryRange | Retrieve sum/minimum/maximum in a given range | O(log n) |
O(n) |
| updateValue | Update value at a specific index | O(log n) |
O(n) |
| rangeQuery | Get aggregated value over a range (e.g., sum, min) | O(log n) |
O(n) |
Example: Range Sum Query with Segment Tree
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
queryRange(node, start, end, l, r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
return this.queryRange(2 * node + 1, start, mid, l, r) +
this.queryRange(2 * node + 2, mid + 1, end, l, r);
}
update(node, start, end, idx, val) {
if (start === end) {
this.tree[node] = val;
} else {
const mid = Math.floor((start + end) / 2);
if (idx <= mid) {
this.update(2 * node + 1, start, mid, idx, val);
} else {
this.update(2 * node + 2, mid + 1, end, idx, val);
}
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
sumRange(left, right) {
return this.queryRange(0, 0, this.n - 1, left, right);
}
updateValue(index, value) {
this.update(0, 0, this.n - 1, index, value);
}
}
// Usage Example
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
console.log(segTree.sumRange(1, 3)); // Output: 15 (3 + 5 + 7)
segTree.updateValue(1, 10); // Update index 1 to 10
console.log(segTree.sumRange(1, 3)); // Output: 22 (10 + 5 + 7)
Note: Segment trees are ideal for handling frequent range queries and updates efficiently, especially in problems involving dynamic arrays where both operations must be fast.
10. Solving 2D Range Queries
A Segment Tree can be extended to handle 2D range queries by building a tree of trees. Each node in the primary segment tree represents a vertical slice of the 2D space, and each such node contains another segment tree for horizontal queries.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Build 2D Segment Tree | Constructs a 2D segment tree from a 2D array of size n×m | O(n * m) |
O(n * m) |
| Query 2D Range | Computes a query over a rectangular region in the 2D array | O(log n * log m) |
O(1) |
| Update Point | Updates a single element in the 2D array | O(log n * log m) |
O(1) |
Example: 2D Range Sum Query
class SegmentTree2D {
constructor(matrix) {
this.n = matrix.length;
this.m = matrix[0].length;
this.tree = Array(this.n * 4).fill().map(() => Array(this.m * 4).fill(0));
this.build(matrix, 0, 0, this.n - 1, this.m - 1, 1, 1);
}
build(matrix, rs, re, cs, ce, nodeRow, nodeCol) {
if (rs > re || cs > ce) return;
if (rs === re && cs === ce) {
this.tree[nodeRow][nodeCol] = matrix[rs][cs];
return;
}
const rm = Math.floor((rs + re) / 2);
const cm = Math.floor((cs + ce) / 2);
this.build(matrix, rs, rm, cs, cm, nodeRow * 2, nodeCol * 2);
this.build(matrix, rs, rm, cm + 1, ce, nodeRow * 2, nodeCol * 2 + 1);
this.build(matrix, rm + 1, re, cs, cm, nodeRow * 2 + 1, nodeCol * 2);
this.build(matrix, rm + 1, re, cm + 1, ce, nodeRow * 2 + 1, nodeCol * 2 + 1);
this.tree[nodeRow][nodeCol] = this.tree[nodeRow * 2][nodeCol * 2] +
this.tree[nodeRow * 2][nodeCol * 2 + 1] +
this.tree[nodeRow * 2 + 1][nodeCol * 2] +
this.tree[nodeRow * 2 + 1][nodeCol * 2 + 1];
}
query(rs, re, cs, ce, nodeRow, nodeCol, rsq, req, csq, ceq) {
if (rs > re || cs > ce || rsq > req || csq > ceq) return 0;
if (rs > rsq || re < req || cs > csq || ce < ceq) return 0;
if (rsq <= rs && req >= re && csq <= cs && ceq >= ce) {
return this.tree[nodeRow][nodeCol];
}
const rm = Math.floor((rs + re) / 2);
const cm = Math.floor((cs + ce) / 2);
return this.query(rs, rm, cs, cm, nodeRow * 2, nodeCol * 2, rsq, req, csq, ceq) +
this.query(rs, rm, cm + 1, ce, nodeRow * 2, nodeCol * 2 + 1, rsq, req, csq, ceq) +
this.query(rm + 1, re, cs, cm, nodeRow * 2 + 1, nodeCol * 2, rsq, req, csq, ceq) +
this.query(rm + 1, re, cm + 1, ce, nodeRow * 2 + 1, nodeCol * 2 + 1, rsq, req, csq, ceq);
}
update(row, col, value) {
this.updatePoint(row, col, value, 0, 0, this.n - 1, this.m - 1, 1, 1);
}
updatePoint(row, col, value, rs, re, cs, ce, nodeRow, nodeCol) {
if (rs > re || cs > ce) return;
if (rs === re && cs === ce) {
this.tree[nodeRow][nodeCol] = value;
return;
}
const rm = Math.floor((rs + re) / 2);
const cm = Math.floor((cs + ce) / 2);
if (row <= rm && col <= cm) {
this.updatePoint(row, col, value, rs, rm, cs, cm, nodeRow * 2, nodeCol * 2);
} else if (row <= rm && col > cm) {
this.updatePoint(row, col, value, rs, rm, cm + 1, ce, nodeRow * 2, nodeCol * 2 + 1);
} else if (row > rm && col <= cm) {
this.updatePoint(row, col, value, rm + 1, re, cs, cm, nodeRow * 2 + 1, nodeCol * 2);
} else {
this.updatePoint(row, col, value, rm + 1, re, cm + 1, ce, nodeRow * 2 + 1, nodeCol * 2 + 1);
}
this.tree[nodeRow][nodeCol] = this.tree[nodeRow * 2][nodeCol * 2] +
this.tree[nodeRow * 2][nodeCol * 2 + 1] +
this.tree[nodeRow * 2 + 1][nodeCol * 2] +
this.tree[nodeRow * 2 + 1][nodeCol * 2 + 1];
}
}
// Example usage:
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const segTree2D = new SegmentTree2D(matrix);
console.log(segTree2D.query(0, 1, 0, 1, 1, 1, 0, 1, 0, 1)); // Sum of 2x2 submatrix
Note: The 2D segment tree is particularly useful for problems involving dynamic updates and range queries in a 2D grid, such as calculating the sum of elements in a rectangular region.
11. Optimizing Space Usage
| Operation | Space Complexity | Notes |
|---|---|---|
| Standard Segment Tree | O(4n) |
Typical implementation uses 4n nodes for safety |
| Optimized Segment Tree | O(2n) |
Uses 2n nodes by avoiding over-allocation |
| Lazy Propagation | O(2n) |
Same as optimized, but with additional lazy nodes |
Example: Space-Optimized Segment Tree
class OptimizedSegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(2 * this.n).fill(0);
this.build(arr);
}
build(arr) {
for (let i = 0; i < this.n; i++) {
this.tree[this.n + i] = arr[i];
}
for (let i = this.n - 1; i > 0; i--) {
this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
}
}
query(l, r) {
let res = 0;
l += this.n;
r += this.n;
while (l <= r) {
if (l % 2 === 1) res += this.tree[l++];
if (r % 2 === 0) res += this.tree[r--];
l /= 2;
r /= 2;
}
return res;
}
update(pos, val) {
pos += this.n;
this.tree[pos] = val;
while (pos > 1) {
pos /= 2;
this.tree[pos] = this.tree[2 * pos] + this.tree[2 * pos + 1];
}
}
}
Note: The optimized version uses exactly
2n nodes, reducing memory overhead compared to the standard O(4n) approach.
12. Combining Multiple Operations
Example: Range Sum and Update
class SegmentTree {
constructor(arr) {
this.n = arr.length;
this.tree = new Array(4 * this.n).fill(0);
this.build(arr, 0, 0, this.n - 1);
}
build(arr, node, start, end) {
if (start === end) {
this.tree[node] = arr[start];
} else {
const mid = Math.floor((start + end) / 2);
this.build(arr, 2 * node + 1, start, mid);
this.build(arr, 2 * node + 2, mid + 1, end);
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
update(node, start, end, idx, val) {
if (start === end) {
this.tree[node] = val;
} else {
const mid = Math.floor((start + end) / 2);
if (idx <= mid) {
this.update(2 * node + 1, start, mid, idx, val);
} else {
this.update(2 * node + 2, mid + 1, end, idx, val);
}
this.tree[node] = this.tree[2 * node + 1] + this.tree[2 * node + 2];
}
}
query(node, start, end, l, r) {
if (r < start || l > end) return 0;
if (l <= start && end <= r) return this.tree[node];
const mid = Math.floor((start + end) / 2);
return this.query(2 * node + 1, start, mid, l, r) +
this.query(2 * node + 2, mid + 1, end, l, r);
}
}
const arr = [1, 3, 5, 7, 9, 11];
const segTree = new SegmentTree(arr);
console.log(segTree.query(0, 0, 5, 1, 3)); // Output: 15 (3 + 5 + 7)
segTree.update(0, 0, 5, 1, 10);
console.log(segTree.query(0, 0, 5, 1, 3)); // Output: 22 (10 + 5 + 7)
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Range Sum Query | Computes sum over a range [l, r] | O(log n) |
O(n) |
| Point Update | Updates value at a specific index | O(log n) |
O(n) |
Note: Segment trees can be adapted to support various operations like min, max, and GCD by modifying the merge function.