Introduction

A Sparse Table is a powerful data structure used for solving Range Queries efficiently when updates are not required. It excels at answering idempotent queries (queries where repeated application does not change the result), such as Range Minimum Query (RMQ), Range Maximum Query (RMaxQ), and Greatest Common Divisor (GCD) queries.

This blog will cover:

1. What is a Sparse Table?

2. How does it work?

3. Building the Sparse Table

4. Querying the Sparse Table

5. Time and Space Complexity

6. Fantastic Examples

7. Comparison with Segment Tree

By the end, you'll have a deep understanding of Sparse Tables and how to implement them in competitive programming!

Understanding the Sparse Table

A Sparse Table is a precomputed data structure that allows answering range queries in O(1) time after an O(N log N) preprocessing step. It is ideal for static arrays where elements don't change after preprocessing.

####

When to Use Sparse Table?

1. When the problem involves static range queries (no updates).

2. When the operation is idempotent (e.g., min, max, GCD).

3. When you need fast queries in O(1) time.

4. When you can afford O(N log N) preprocessing time and O(N log N) space.

####

How Does the Sparse Table Work?

The Sparse Table stores precomputed answers for overlapping subarrays of power-of-two lengths. Using this precomputed information, we can answer queries in constant time.

We define st[i][j], where:

1. i represents the starting index of the range.

2. j represents the length of the subarray as 2^j (powers of two).

For example, if j = 3, the range size is 2^3 = 8, meaning st[i][3] stores the result for the range [i, i + 7].

####

Building the Table

We fill st[i][j] based on the idempotent property:

st[i][j]=operation(st[i][j−1],st[i+2^j−1][j−1])

This formula ensures that every interval is built using two smaller, previously computed intervals.

Implementation of Sparse Table (Range Minimum Query)

Let's now implement a Sparse Table for Range Minimum Query (RMQ).

class SparseTable { constructor(arr) { this.n = arr.length; this.log = new Uint8Array(this.n + 1); this.st = Array.from({ length: this.n }, () => new Int32Array(20));

// Compute logarithm values
            for (let i = 2; i <= this.n; i++) this.log[i] = this.log[i >> 1] + 1;

            // Initialize Sparse Table with original array values
            for (let i = 0; i < this.n; i++) this.st[i][0] = arr[i];

            // Fill the table
            for (let j = 1;
                    (1 << j) <= this.n; j++) {
                    for (let i = 0; i + (1 << j) <= this.n; i++) {
                            this.st[i][j] = Math.min(this.st[i][j - 1], this.st[i + (1 << (j - 1))][j - 1]);
                    }
            }
    }

    // Query for minimum in range [L, R]
    query(L, R) {
            let j = this.log[R - L + 1];
            return Math.min(this.st[L][j], this.st[R - (1 << j) + 1][j]);
    }

}

// Usage let arr = [1, 3, 5, 7, 9, 2, 6, 4, 8, 0]; let st = new SparseTable(arr); console.log(st.query(2, 5)); // Output: 2 console.log(st.query(0, 9)); // Output: 0

Querying the Sparse Table

==============================

For a given range [L, R], we use the largest power of two segment that fits within the range. This means:

answer=min(st[L][j],st[R−2^j+1][j])

where:

1. j=floor(log(R−L+1))

2. We use two overlapping intervals to cover the entire range.

Why Does Querying Take O(1) ?

Since we're only performing two lookups and a Math.min() operation, the time complexity is O(1).

Space and Time Complexity

Operation

Building Table => O(n log n)

Querying => O(1)

Space Complexity => O(n log n)

Sparse Table is extremely efficient for static range queries but is not suitable for problems requiring modifications.

Examples of Sparse Table in Action

Example 1: Range Maximum Query

We replace Math.min() with Math.max(), and the implementation remains the same.

Example 2: Range GCD Query

Instead of min/max, we use gcd(a, b):

function gcd(a, b) { while (b)[a, b] = [b, a % b]; return a; }

Then, replace Math.min() in st[i][j] computation with gcd().

Segment Tree vs. Sparse Table

Feature

Preprocessing Time => O(n log n)(sparse Table) => O(n)(Segment Tree)

Query Time => O(1)(sparse Table) => O(log n)(Segment Tree)

Update Time => Not Possible(sparse Table) => O(log n)(Segment Tree)

Space Complexity => O(n log n)(sparse Table) => O(n)(Segment Tree)

Sparse Tables win when:

You have static data (no updates).

You need fast queries (O(1) vs. O(log N) in Segment Tree).

Conclusion

Sparse Tables are super-efficient for answering range queries when updates are not needed. By precomputing power-of-two segments, we ensure queries can be answered in constant time.

Key Takeaways:

Precompute in O(n log n), Query in O(1).

####

Works only for idempotent operations like min, max, GCD.

####

Not suitable for problems requiring updates.

####

Better than Segment Tree for static queries.

Try implementing Sparse Tables for different problems like:

1. LCM Queries

2. Bitwise AND Queries

3. Sum Queries (with a slight tweak)

By mastering Sparse Tables, you unlock a powerful technique for fast range queries in competitive programming!

Happy Coding!

=============

Min Heap & Max Heap...

Heap is a fundamental data structure that is widely used in competitive programming, especially in problems that require efficient retrieval of the smallest or largest elements in a dataset.

####

JavaScript does not have a built-in heap implementation, but we can efficiently implement Min Heap and Max Heap using an array and a comparator function.

In this blog, we will cover:

• What is a Heap?

• Min Heap & Max Heap with Implementation in JavaScript (Node.js).

• Advantages & Disadvantages of Heaps.

• When to Use Heaps in Codeforces Problems.

• Why & When NOT to Use Heaps.

1. What is a Heap?

A Heap is a special type of binary tree-based data structure that satisfies the heap property:

• Min Heap: The parent node is always smaller than or equal to its child nodes.
• Max Heap: The parent node is always larger than or equal to its child nodes.

This property ensures that the smallest (Min Heap) or largest (Max Heap) element is always at the root, making heaps extremely useful for priority-based tasks.

2. Min Heap & Max Heap Implementation in JavaScript (Node.js)

Since JavaScript does not provide a built-in heap, we implement it using an array-based binary heap with the following operations:

• Insert (push)
• Extract Min/Max (pop)
• Heapify (maintain heap property)

Min Heap Implementation

class MinHeap { constructor() { this.h = []; }

push(v) {
            this.h.push(v);
            this.#heapifyUp();
    }

    pop() {
            if (this.h.length === 0) return null;
            if (this.h.length === 1) return this.h.pop();
            const min = this.h[0];
            this.h[0] = this.h.pop();
            this.#heapifyDown();
            return min;
    }

    top() {
            return this.h.length ? this.h[0] : null;
    }

    size() {
            return this.h.length;
    }

    #heapifyUp() {
            let i = this.h.length - 1;
            while (i > 0) {
                    let p = Math.floor((i - 1) / 2);
                    if (this.h[p] <= this.h[i]) break;
        [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
                    i = p;
            }
    }

    #heapifyDown() {
            let i = 0;
            while (2 * i + 1 < this.h.length) {
                    let j = 2 * i + 1;
                    if (j + 1 < this.h.length && this.h[j + 1] < this.h[j]) j++;
                    if (this.h[i] <= this.h[j]) break;
        [this.h[i], this.h[j]] = [this.h[j], this.h[i]];
                    i = j;
            }
    }

}

// Usage:

let heap = new MinHeap(); heap.push(5); heap.push(3); heap.push(8); heap.push(1); console.log(heap.pop()); // 1 console.log(heap.pop()); // 3

Max Heap Implementation

A Max Heap follows the same structure as a Min Heap, but the parent nodes must always be greater than the child nodes.

class MaxHeap { constructor() { this.h = []; }

push(v) {
            this.h.push(v);
            this.#heapifyUp();
    }

    pop() {
            if (this.h.length === 0) return null;
            if (this.h.length === 1) return this.h.pop();
            const max = this.h[0];
            this.h[0] = this.h.pop();
            this.#heapifyDown();
            return max;
    }

    top() {
            return this.h.length ? this.h[0] : null;
    }

    size() {
            return this.h.length;
    }

    #heapifyUp() {
            let i = this.h.length - 1;
            while (i > 0) {
                    let p = Math.floor((i - 1) / 2);
                    if (this.h[p] >= this.h[i]) break;
        [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
                    i = p;
            }
    }

    #heapifyDown() {
            let i = 0;
            while (2 * i + 1 < this.h.length) {
                    let j = 2 * i + 1;
                    if (j + 1 < this.h.length && this.h[j + 1] > this.h[j]) j++;
                    if (this.h[i] >= this.h[j]) break;
        [this.h[i], this.h[j]] = [this.h[j], this.h[i]];
                    i = j;
            }
    }

}

// Usage:

let heap = new MaxHeap(); heap.push(5); heap.push(3); heap.push(8); heap.push(1); console.log(heap.pop()); // 8 console.log(heap.pop()); // 5

3. Advantages & Disadvantages of Heaps

Pros (Why Use a Heap?)

• Efficient Priority Queue: Inserting and extracting the smallest/largest element is O(log N).
• Useful for Shortest Path & Scheduling: Heaps are widely used in Dijkstra’s Algorithm and task scheduling problems.
• Memory Efficient: Unlike balanced BSTs, heaps require less memory overhead due to the array-based structure.

Cons (When NOT to Use a Heap?)

• Not Ideal for Searching: Finding an arbitrary element is O(N), unlike BSTs where searching is O(log N).
• Limited Sorting Use: Although Heap Sort exists, it’s generally outperformed by Merge Sort & Quick Sort in practice.
• No Ordered Traversal: Unlike BSTs, you cannot traverse elements in sorted order efficiently.

4. When to Use Heaps in Codeforces?

Common Problem Scenarios

Problem Type ================================================== Use Case Find k-th smallest/largest element ============================ Min Heap / Max Heap Priority-based tasks (Dijkstra’s Algorithm, Huffman Coding) === Min Heap Merge k Sorted Lists ========================================== Min Heap Sliding Window Maximum ======================================== Max Heap Job Scheduling Problems ======================================= Min Heap

Example: Finding k-th Smallest Element

let heap = new MinHeap(); for (let x of [7, 10, 4, 3, 20, 15]) heap.push(x); let k = 3; while (--k) heap.pop(); console.log(heap.pop()); // 7

5. Why & When NOT to Use Heaps?

• If You Need Fast Searching: Use BSTs or Hash Maps for O(1) / O(log N) searches.
• If You Need Ordered Data: Use a Balanced BST (e.g., AVL, Red-Black Tree) instead.
• For Sorting Large Arrays: Use Quick Sort or Merge Sort instead of Heap Sort.

10 Scenarios Where Heaps Are Used in Competitive Programming

• Finding the k-th Smallest or k-th Largest Element
• Merging k Sorted Arrays
• Implementing a Priority Queue
• Dijkstra’s Algorithm (Shortest Path in a Graph)
• Prim’s Algorithm (Minimum Spanning Tree — MST)
• Top k Frequent Elements (Frequency Counting)
• Median of a Stream (Dynamic Median Calculation)
• Job Scheduling with Deadlines (Greedy Scheduling)
• Sliding Window Maximum (Finding Max in Every Window of Size k)
• Huffman Encoding (Data Compression — Huffman Coding Tree)

Conclusion

Min Heap and Max Heap are powerful tools in competitive programming, particularly for priority-based tasks, shortest path algorithms, and scheduling problems. However, they should not be used for searching or problems requiring sorted order access. By implementing a heap efficiently in JavaScript, you can significantly improve your performance on Codeforces.

Happy Coding !
             Youtube : (http://www.youtube.com/@code-with-Bharadwaj)

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.

1. 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)

1. 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!

This blog post delves into a well-structured Node.js code template designed for performance optimization, particularly suited for competitive programming challenges.

We'll break down the code line by line, explaining its purpose and how it contributes to efficient input/output handling and potentially faster execution.

You'll also gain insights on submitting solutions in a Node.js environment.

Code Breakdown

1. Buffer Allocation and Initialization:

let inputBuffer = Buffer.allocUnsafe(1e7); let inputIndex = 0, inputLength = 0; let outputBuffer = Buffer.allocUnsafe(1e7); let outputIndex = 0;

• Buffer.allocUnsafe(1e7): Creates two fixed-size buffers, inputBuffer and outputBuffer, each with a capacity of 10 million bytes (10 MB). These buffers will store input and output data, respectively, for efficient memory management.

• inputIndex and inputLength: These variables track the current position within the inputBuffer and the number of bytes read from standard input (stdin), respectively.

• outputIndex: Tracks the current position within the outputBuffer where output data is written.

1. Reading Input (stdin):

const fs = require('fs'); inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

• fs.readSync: This function synchronously reads data from standard input (stdin), which typically refers to the user's console input.

• process.stdin.fd: Represents the file descriptor (fd) for standard input.

• inputBuffer: The buffer where the read data will be stored.

• 0: Starting offset within the inputBuffer for writing the read data.

• inputBuffer.length: Maximum number of bytes to read from stdin.

• null: No additional options are specified.

• inputLength: After the read operation, inputLength is assigned the number of bytes successfully read from stdin. This value will be used to determine the extent of valid data in the inputBuffer.

1. readInt Function:

function readInt() { let num = 0, sign = 1; while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) { if (inputBuffer[inputIndex] === 45) sign = -1; inputIndex++; } while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) { num = num * 10 + (inputBuffer[inputIndex++] — 48); } return num * sign; }

• Purpose: This function reads an integer value from the inputBuffer, handling both positive and negative numbers.

• Logic:

• Initializes num to 0 and sign to 1 (assuming a positive number initially).

• Skips non-numeric characters (anything less than 48 or greater than 57 in ASCII code, which corresponds to '0' to '9') at the beginning of the input, checking for a negative sign (45 in ASCII, '-') if encountered.

• Iterates through the inputBuffer until the end of the numeric input is reached, accumulating individual digits into the num variable by multiplying the current number by 10 and adding the new digit (obtained by subtracting 48 from the corresponding ASCII code). Accounts for the negative sign if encountered earlier.

• Returns the final integer value after sign adjustment.

1. writeInt Function:

let isFirstInLine = true; function writeInt(value, isLast = false) { if (!isFirstInLine) { outputBuffer[outputIndex++] = 32; // Add a space before subsequent numbers } if (value < 0) { outputBuffer[outputIndex++] = 45; value = -value; } let digits = []; do { digits.push(value % 10); value = Math.floor(value / 10); } while (value > 0); for (let i = digits.length — 1; i >= 0; i--) { outputBuffer[outputIndex++] = 48 + digits[i]; // Convert digit to ASCII character } isFirstInLine = isLast; if (isLast) { outputBuffer[outputIndex++] = 10; // Add a newline character after the last number isFirstInLine = true; } }

1. Writing Output to stdout:

const v8Flags = [ '--turbo-inline-threshold=500',
'--max-old-space-size=256',
'--no-lazy',
'--optimize-for-size',
'--unbox-small-integers',
'--predictable',
'--no-use-idle-notification',
'--single-generation',
'--compact-maps',
'--always-compact'
];

if (v8Flags.length > 0) { process.execArgv.push('--v8-options=' + v8Flags.join(' ')); }

let a = readInt(); let b = readInt(); writeInt(Math.floor(a / 10)); writeInt(a % 10, true); writeInt(Math.floor(b / 10)); writeInt(b % 10, true); fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));

• V8 Flags: These flags are used to optimize the V8 JavaScript engine for performance. They are specific to Node.js and can significantly impact execution speed.

• Reading Input:

• readInt() is called twice to read two integer values, a and b, from the input.

• Processing and Writing Output:

• Math.floor(a / 10) and a % 10 extract the tens and units digits of a, respectively.

• Math.floor(b / 10) and b % 10 extract the tens and units digits of b, respectively.

• writeInt() is called four times to write the extracted digits to the outputBuffer, with appropriate spacing and newline characters.

• Finally, fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex)) writes the contents of the outputBuffer up to the outputIndex to standard output (stdout), which is typically displayed in the console.

Submitting Solutions in Node.js

To submit a Node.js solution to a platform like Codeforces, you typically need to create a script that takes input from stdin, processes it, and writes the output to stdout. Here's a general approach:

• Create a Node.js file: Write your solution code, including the input/output functions and the main logic, in a .js file.

• Prepare the Input: Ensure that the input format matches the problem's requirements. If the input is provided in a file, you can use fs.readFileSync to read it. For interactive problems, you might need to handle input line by line using readline.

• Run the Script: Execute the script using the Node.js runtime: node your_script.js.

• Redirect Input/Output: If the platform requires specific input/output methods, you might need to redirect stdin and stdout using command-line arguments or environment variables.

• Submit the Solution: Follow the platform's guidelines to submit your .js file and any necessary configuration files.

Additional Tips for Optimization

• Profiling: Use Node.js profiling tools to identify performance bottlenecks in your code.

• Memory Management: Be mindful of memory usage, especially when dealing with large input/output data.

• Algorithm and Data Structure Choice: Select efficient algorithms and data structures for your problem.

• V8 Flags: Experiment with different V8 flags to find the optimal configuration for your specific use case.

• Code Clarity: Write clean and readable code to facilitate debugging and optimization. By understanding the code template and applying these optimization techniques, you can create efficient Node.js solutions for competitive programming and other performance-critical applications.

Complete Template ( Buffer based Fast IO ( Node.js by Bharadwaj ) )

let inputBuffer = Buffer.allocUnsafe(1e7); let inputIndex = 0, inputLength = 0; let outputBuffer = Buffer.allocUnsafe(1e7); let outputIndex = 0;

const fs = require('fs'); inputLength = fs.readSync(process.stdin.fd, inputBuffer, 0, inputBuffer.length, null);

function readInt() { let num = 0, sign = 1; while (inputBuffer[inputIndex] < 48 || inputBuffer[inputIndex] > 57) { if (inputBuffer[inputIndex] === 45) sign = -1; inputIndex++; } while (inputIndex < inputLength && inputBuffer[inputIndex] >= 48 && inputBuffer[inputIndex] <= 57) { num = num * 10 + (inputBuffer[inputIndex++] — 48); } return num * sign; }

let isFirstInLine = true; function writeInt(value, isLast = false) { if (!isFirstInLine) { outputBuffer[outputIndex++] = 32; } if (value < 0) { outputBuffer[outputIndex++] = 45; value = -value; } let digits = []; do { digits.push(value % 10); value = Math.floor(value / 10); } while (value > 0); for (let i = digits.length — 1; i >= 0; i--) { outputBuffer[outputIndex++] = 48 + digits[i]; } isFirstInLine = isLast; if (isLast) { outputBuffer[outputIndex++] = 10; isFirstInLine = true; } }

const v8Flags = [ '--turbo-inline-threshold=500',
'--max-old-space-size=256',
'--no-lazy',
'--optimize-for-size',
'--unbox-small-integers',
'--predictable',
'--no-use-idle-notification',
'--single-generation',
'--compact-maps',
'--always-compact'
];

if (v8Flags.length > 0) { process.execArgv.push('--v8-options=' + v8Flags.join(' ')); }

let a = readInt(); let b = readInt(); writeInt(Math.floor(a / 10)); writeInt(a % 10, true); writeInt(Math.floor(b / 10)); writeInt(b % 10, true); fs.writeSync(process.stdout.fd, outputBuffer.slice(0, outputIndex));