JavaScript Coding Test Course, Segment Tree

Problem Description

Problem: Calculate the Sum of a Given Range

An array arr containing n integers is given,
and you need to write a function to handle the following queries:

  • 1. update(index, value) : Updates the indexth value in the array arr to value.
  • 2. rangeSum(left, right) : Calculates the sum from the leftth to the rightth (0-indexing) in the array arr.

Use the given array and queries to efficiently handle the requirements of update and rangeSum.
The size of the array is up to 10^5 and the number of queries is also up to 10^5.

Solution Method

This problem requires efficiently calculating range sums and processing updates, so we can use a Segment Tree.
A Segment Tree is a binary tree-based data structure that stores the given array in intervals (for range sum queries).

Definition of Segment Tree

A Segment Tree has the following properties:

  • Each node stores information about one array interval. This information can be set as the sum, minimum, maximum, etc. of the interval.
  • The height of the tree is O(log n), meaning that both query and update operations take O(log n) time.

Steps to Implement a Segment Tree

To implement a Segment Tree, follow these steps:

  1. Initialization: Initialize the Segment Tree based on the given array.
  2. Range Sum Query: Recursively retrieve the nodes necessary to calculate the sum for a specific interval.
  3. Update: Update the value at a specific index and refresh the relevant segment nodes.

JavaScript Code Implementation


class SegmentTree {
    constructor(arr) {
        this.n = arr.length;
        this.tree = new Array(this.n * 4);
        this.build(arr, 0, 0, this.n - 1);
    }

    build(arr, node, start, end) {
        if (start === end) {
            // Store integer value at leaf node
            this.tree[node] = arr[start];
        } else {
            const mid = Math.floor((start + end) / 2);
            // Define left child
            this.build(arr, node * 2 + 1, start, mid);
            // Define right child
            this.build(arr, node * 2 + 2, mid + 1, end);
            // Define parent node as the sum of both children
            this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
        }
    }

    rangeSum(left, right) {
        return this.sum(0, 0, this.n - 1, left, right);
    }

    sum(node, start, end, left, right) {
        if (right < start || end < left) {
            // Return 0 if requested range does not overlap
            return 0;
        }
        if (left <= start && end <= right) {
            // Return node if requested range is fully included
            return this.tree[node];
        }
        const mid = Math.floor((start + end) / 2);
        const leftSum = this.sum(node * 2 + 1, start, mid, left, right);
        const rightSum = this.sum(node * 2 + 2, mid + 1, end, left, right);
        return leftSum + rightSum;
    }

    update(index, value) {
        this.updateValue(0, 0, this.n - 1, index, value);
    }

    updateValue(node, start, end, index, value) {
        if (start === end) {
            // Update leaf node
            this.tree[node] = value;
        } else {
            const mid = Math.floor((start + end) / 2);
            if (index <= mid) {
                this.updateValue(node * 2 + 1, start, mid, index, value);
            } else {
                this.updateValue(node * 2 + 2, mid + 1, end, index, value);
            }
            // Update parent node
            this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];
        }
    }
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11];
const segmentTree = new SegmentTree(arr);
console.log(segmentTree.rangeSum(1, 3)); // 15
segmentTree.update(1, 10);
console.log(segmentTree.rangeSum(1, 3)); // 22

Conclusion

The Segment Tree is a powerful tool for efficiently handling the range sum of arrays.
This data structure allows for updates and range sum calculations with a time complexity of O(log n).
When faced with complex problems in practice, using a Segment Tree can provide many advantages.

Additional Practice Problems

Try practicing the following problems:

  • Use a Segment Tree to find the minimum value in a given array
  • Add a query to add a specific value over an interval
  • Find the maximum value using a Segment Tree