Problem Statement

Given an integer array nums, handle multiple queries of the following types:

1. Update the value of an element in nums.
2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

• NumArray(int[] nums) Initializes the object with the integer array nums.
• void update(int index, int val) Updates the value of nums[index] to be val.
• int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

LeetCode

https://leetcode.com/problems/range-sum-query-mutable/

Constraints

1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 10^4 calls will be made to update and sumRange.

Examples

Example 1:

Input
:
      ["NumArray", "sumRange", "update", "sumRange"]
      [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]

Output:
 [null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Different Approaches

1️⃣ Segment Tree

Intuition:

Suppose you're given an array and need to perform two operations efficiently:

1. Update: Change the value at a specific index.
2. Range Sum Query: Find the sum of elements between indices l and r.

A naive approach:

• For sumRange(l, r): Loop through the array → O(n)
• For update(index, val): Just modify that index → O(1)

Problem: If you have many queries, the sumRange operation will become a bottleneck.

🚀 Goal:

We want both update and sumRange operations to run in logarithmic time → O(log n).

That’s where the Segment Tree comes in.

🧠 Approach

What is a Segment Tree?

A Segment Tree is a binary tree:

• Each node represents a range of the array.
• The root node represents the whole array.
• Leaf nodes represent single elements.
• Internal nodes represent sum of child nodes (subranges).

🔧 Operations

1. buildTree (Recursive Construction)
   1. Divide the array into two halves until each segment has only one element.
   2. Merge the segments by summing them up into parent nodes.
2. sumRange(start, end)
   1. Traverse the tree:
      1. No Overlap: return 0.
      2. Complete Overlap: return node value.
      3. Partial Overlap: recurse on both left and right children.
3. update(index, value)
   1. Traverse the tree to reach the leaf node of that index.
   2. Change the value and update its ancestors accordingly.

Code:

class NumArray {
public:
    vector<int> segTree;   // Segment Tree array
    int n;                 // Size of the original input array

    // Constructor to initialize the segment tree
    NumArray(vector<int>& nums) {
        n = nums.size();
        if (n == 0) return;

        segTree.resize(4 * n);  // Allocate enough space for segment tree
        buildTree(0, 0, n - 1, nums);
    }

    // Public method to update the value at index `index` to `val`
    void update(int index, int val) {
        updateUtil(index, val, 0, 0, n - 1);
    }

    // Public method to return the sum of elements in range [left, right]
    int sumRange(int left, int right) {
        return sumRangeUtil(left, right, 0, 0, n - 1);
    }

private:
    // Build the segment tree recursively
    void buildTree(int node, int l, int r, vector<int>& nums) {
        if (l == r) {
            segTree[node] = nums[l];  // Leaf node stores the actual element
            return;
        }

        int mid = (l + r) / 2;

        // Build left and right subtrees
        buildTree(2 * node + 1, l, mid, nums);
        buildTree(2 * node + 2, mid + 1, r, nums);

        // Internal node stores the sum of both children
        segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    }

    // Utility function to update the segment tree at position `index`
    void updateUtil(int index, int val, int node, int l, int r) {
        if (l == r) {
            segTree[node] = val;  // Update the value at the leaf node
            return;
        }

        int mid = (l + r) / 2;

        if (index <= mid) {
            updateUtil(index, val, 2 * node + 1, l, mid);        // Go to left child
        } else {
            updateUtil(index, val, 2 * node + 2, mid + 1, r);     // Go to right child
        }

        // After updating child, update current node
        segTree[node] = segTree[2 * node + 1] + segTree[2 * node + 2];
    }

    // Utility function to get the sum in range [start, end]
    int sumRangeUtil(int start, int end, int node, int l, int r) {
        // No overlap
        if (end < l || start > r) {
            return 0;
        }

        // Complete overlap
        if (start <= l && end >= r) {
            return segTree[node];
        }

        // Partial overlap
        int mid = (l + r) / 2;
        int leftSum = sumRangeUtil(start, end, 2 * node + 1, l, mid);
        int rightSum = sumRangeUtil(start, end, 2 * node + 2, mid + 1, r);
        return leftSum + rightSum;
    }
};

Complexity Analysis: