307. Range Sum Query – Mutable | Leetcode Solutions

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

from typing import List

class NumArray:
    def __init__(self, nums: List[int]):
        """
        Initializes the NumArray object with the given integer array.
        It builds a segment tree to allow efficient range sum queries and updates.
        """
        self.n = len(nums)
        # Initialize the segment tree with size 2 * n (for zero-based indexing)
        self.tree = [0] * (2 * self.n)
        
        # Build the segment tree by copying the input array to the leaves
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        
        # Populate internal nodes of the tree (from the leaves up to the root)
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def update(self, index: int, val: int) -> None:
        """
        Updates the value of nums[index] to be val.
        """
        # Set the value at the leaf node
        pos = index + self.n
        self.tree[pos] = val
        
        # Move up the tree and update the parent nodes
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def sumRange(self, left: int, right: int) -> int:
        """
        Returns the sum of the elements of nums between indices left and right inclusive.
        """
        # Convert the indices to correspond to the leaves in the segment tree
        left += self.n
        right += self.n
        sum_ = 0
        
        while left <= right:
            # If left is a right child, add its value and move to the next segment
            if left % 2 == 1:
                sum_ += self.tree[left]
                left += 1
            # If right is a left child, add its value and move to the previous segment
            if right % 2 == 0:
                sum_ += self.tree[right]
                right -= 1
            # Move to the parent nodes
            left //= 2
            right //= 2
        
        return sum_

#include <vector>

using namespace std;

class NumArray {
public:
    // Constructor that initializes the segment tree from the input array
    NumArray(vector<int>& nums) {
        n = nums.size(); // Size of the original array
        tree.resize(2 * n); // Segment tree size is 2 * n (for zero-based indexing)
        
        // Initialize the leaves (the second half of the tree)
        for (int i = 0; i < n; ++i) {
            tree[n + i] = nums[i];
        }
        
        // Build the segment tree by filling the internal nodes
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[2 * i] + tree[2 * i + 1]; // Parent node is the sum of its two children
        }
    }
    
    // Function to update the value at a specific index
    void update(int index, int val) {
        int pos = index + n; // Convert the index to the leaf node position in the segment tree
        tree[pos] = val; // Update the leaf node with the new value
        
        // Now propagate the change up the tree to maintain the correct sums
        while (pos > 1) {
            pos /= 2; // Move to the parent node
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1]; // Update parent node by summing its two children
        }
    }
    
    // Function to calculate the sum of the range [left, right] inclusive
    int sumRange(int left, int right) {
        left += n;  // Convert left index to corresponding leaf node
        right += n; // Convert right index to corresponding leaf node
        int sum = 0; // Variable to store the sum
        
        while (left <= right) {
            // If left is a right child, include its value and move to the next segment
            if (left % 2 == 1) {
                sum += tree[left];
                ++left;
            }
            
            // If right is a left child, include its value and move to the previous segment
            if (right % 2 == 0) {
                sum += tree[right];
                --right;
            }
            
            // Move to the parent nodes
            left /= 2;
            right /= 2;
        }
        
        return sum; // Return the total sum
    }

private:
    int n; // Size of the original array
    vector<int> tree; // Segment tree
};

var NumArray = function(nums) {
    this.n = nums.length; // Size of the original array
    this.tree = new Array(2 * this.n).fill(0); // Initialize the segment tree (size 2 * n)

    // Build the segment tree by filling the leaf nodes with the input array
    for (let i = 0; i < this.n; i++) {
        this.tree[this.n + i] = nums[i];
    }

    // Build the internal nodes of the tree (parent nodes) by summing the children
    for (let i = this.n - 1; i > 0; --i) {
        this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
    }
};


NumArray.prototype.update = function(index, val) {
    // Convert the index to the corresponding leaf node in the segment tree
    let pos = index + this.n;
    this.tree[pos] = val; // Update the leaf node with the new value

    // Propagate the change up the tree to maintain correct sums
    while (pos > 1) {
        pos = Math.floor(pos / 2); // Move to the parent node
        this.tree[pos] = this.tree[2 * pos] + this.tree[2 * pos + 1]; // Update the parent node by summing its children
    }
};


NumArray.prototype.sumRange = function(left, right) {
    // Convert the indices to corresponding leaf nodes in the segment tree
    left += this.n;
    right += this.n;
    let sum = 0; // Variable to store the range sum

    while (left <= right) {
        // If left is a right child, include its value and move to the next segment
        if (left % 2 === 1) {
            sum += this.tree[left];
            left++;
        }
        // If right is a left child, include its value and move to the previous segment
        if (right % 2 === 0) {
            sum += this.tree[right];
            right--;
        }
        // Move to the parent nodes
        left = Math.floor(left / 2);
        right = Math.floor(right / 2);
    }

    return sum; // Return the total sum for the range
};

class NumArray {
    private int[] tree; // Segment tree to store range sums
    private int n;      // Size of the input array

    /**
     * Initializes the NumArray object with the given integer array nums.
     * The segment tree is built based on the input array to allow efficient range queries and updates.
     */
    public NumArray(int[] nums) {
        n = nums.length;
        tree = new int[2 * n]; // Segment tree size is 2 * n (for zero-based indexing)
        
        // Copy the input array to the leaves of the segment tree
        for (int i = 0; i < n; i++) {
            tree[n + i] = nums[i];
        }

        // Build the segment tree by filling in the internal nodes (parent nodes)
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1]; // Each parent node is the sum of its two children
        }
    }

    /**
     * Updates the value at index index to val.
     * The segment tree is updated accordingly to maintain correct range sums.
     */
    public void update(int index, int val) {
        // Set the value at the corresponding leaf node in the segment tree
        int pos = index + n;
        tree[pos] = val;

        // Propagate the change up the tree to update the affected range sums
        while (pos > 1) {
            pos /= 2; // Move to the parent node
            tree[pos] = tree[2 * pos] + tree[2 * pos + 1]; // Update the parent node by summing its children
        }
    }

    /**
     * Returns the sum of elements in the range [left, right] (inclusive).
     * This is done efficiently using the segment tree.
     */
    public int sumRange(int left, int right) {
        // Convert the indices to corresponding leaf nodes in the segment tree
        left += n;
        right += n;
        int sum = 0; // Variable to store the range sum

        // While the left index is less than or equal to the right index
        while (left <= right) {
            // If left is a right child, include its value in the sum and move to the next segment
            if (left % 2 == 1) {
                sum += tree[left];
                left++;
            }

            // If right is a left child, include its value in the sum and move to the previous segment
            if (right % 2 == 0) {
                sum += tree[right];
                right--;
            }

            // Move both left and right indices to their parent nodes
            left /= 2;
            right /= 2;
        }

        return sum; // Return the computed sum for the range
    }
}