/* -------------------------------------------------------- / / ( The Authentic JS CodeBuff ) ____ _ _ | _ ) |_ __ _ _ _ __ _ | |_ __ ____ _ (_) | _ \ ' \/ _| '_/ _ / \ V V / _ || | |/_||___,_|_| __,___,_|_/_/__,_|/ | |__/ / / --------------------------------------------------------- / / Youtube: https://youtube.com/@code-with-Bharadwaj / / Github : https://github.com/Manu577228 / / ----------------------------------------------------------- */
Hey Codeforces community!
Tackling range queries efficiently is a cornerstone of competitive programming.Two powerful data structures that often come to the rescue are Segment Trees and Fenwick Trees (also known as Binary Indexed Trees). This blog post will dive deep into these structures, explaining their concepts and implementations in JavaScript/Node.js with clear examples.
Why Range Queries?
Range queries involve operations on a contiguous subarray (a range) of an array. Common examples include:
Sum Queries: Finding the sum of elements within a given range.
Minimum/Maximum Queries: Finding the minimum/maximum element within a range.
Update Queries: Updating elements within a given range.
- Segment Trees
A Segment Tree is a binary tree-based data structure that efficiently handles range queries. Each node in the Segment Tree represents a range of the original array.
- Construction:
The root node represents the entire array. Each internal node represents a subrange, with its left child representing the left half and its right child representing the right half. Leaf nodes represent individual elements of the original array.
- Querying:
To query a range, we traverse the tree, visiting only the nodes that overlap with the query range.
- Updating:
To update an element, we traverse down to the corresponding leaf node and update its value. The changes propagate upwards, updating the values of parent nodes.
class SegmentTree {
constructor(arr) { this.arr = arr; this.tree = new Array(4 * arr.length); // Worst-case size of the tree this.build(0, 0, arr.length — 1); }
build(index, start, end) { if (start === end) { this.tree[index] = this.arr[start]; return; }
const mid = Math.floor((start + end) / 2); this.build(2 * index + 1, start, mid); this.build(2 * index + 2, mid + 1, end); this.tree[index] = this.tree[2 * index + 1] + this.tree[2 * index + 2]; // Sum example
}
query(index, start, end, left, right) { if (right < start || end < left) { return 0; // No overlap } if (left <= start && end <= right) { return this.tree[index]; // Complete overlap } const mid = Math.floor((start + end) / 2); const leftSum = this.query(2 * index + 1, start, mid, left, right); const rightSum = this.query(2 * index + 2, mid + 1, end, left, right); return leftSum + rightSum; // Combine results }
update(index, start, end, updateIndex, value) { if (start === end) { this.tree[index] = value; this.arr[updateIndex] = value; return; }
const mid = Math.floor((start + end) / 2);
if (updateIndex <= mid) {
this.update(2 * index + 1, start, mid, updateIndex, value);
} else {
this.update(2 * index + 2, mid + 1, end, updateIndex, value);
}
this.tree[index] = this.tree[2 * index + 1] + this.tree[2 * index + 2]; // Update sum} }
Usage:
const arr = [1, 3, 5, 7, 9, 11];
const segmentTree = new SegmentTree(arr); console.log(segmentTree.query(0, 0, arr.length — 1, 1, 4)); // Output: 25 (3 + 5 + 7 + 9) segmentTree.update(0, 0, arr.length — 1, 2, 10); // Update arr[2] to 10 console.log(segmentTree.query(0, 0, arr.length — 1, 1, 4)); // Output: 30 (3 + 10 + 7 + 9)
- Fenwick Trees (Binary Indexed Trees)
Fenwick Trees are a more compact and often faster alternative to Segment Trees for certain types of range queries, specifically prefix sum queries and updates.
- Concept:
A Fenwick Tree uses a clever indexing scheme to implicitly represent prefix sums. Each element in the tree stores information about a specific range of the original array.
- Operations: Both querying and updating are performed using bit manipulation, making them very efficient.
class FenwickTree { constructor(arr) { this.arr = arr; this.tree = new Array(arr.length + 1).fill(0); for (let i = 0; i < arr.length; i++) { this.update(i, arr[i]); } }
update(index, value) { index++; // 1-based indexing while (index <= this.arr.length) { this.tree[index] += value; index += index & -index; // Lowest set bit } }
query(index) { index++; // 1-based indexing let sum = 0; while (index > 0) { sum += this.tree[index]; index -= index & -index; // Lowest set bit } return sum; }
rangeSum(left, right) { return this.query(right) — this.query(left — 1); } }
Usage:
const arr = [1, 3, 5, 7, 9, 11];
const fenwickTree = new FenwickTree(arr); console.log(fenwickTree.rangeSum(1, 4)); // Output: 25 (3 + 5 + 7 + 9) fenwickTree.update(2, 5); // Update arr[2] by adding 5 (making it 10) console.log(fenwickTree.rangeSum(1, 4)); // Output: 30 (3 + 10 + 7 + 9)
Comparison:
Space Complexity: Segment Trees can use up to 4n space, while Fenwick Trees use n+1 space.
Time Complexity: Both have O(log n) time complexity for queries and updates. Fenwick Trees are often slightly faster in practice due to simpler operations.
Use Cases:
Segment Trees are more versatile and can handle a wider range of operations (min, max, etc.).
Fenwick Trees are best suited for prefix sum queries and updates.
Conclusion:
Segment Trees and Fenwick Trees are indispensable tools for any competitive programmer. Understanding their implementations and knowing when to use them can significantly improve your problem-solving abilities.
Happy coding!
