Range Sum Query Mutable

                                            
class NumArray {
public:
    NumArray(vector<int>& nums) {
        data = nums;
        int size = nums.size();
        bit.resize(size + 1);
        for (int i = 0; i < size; i++) {
            updateBIT(i, nums[i]);
        }
    }
    
    void update(int index, int val) {
        int diff = val - data[index];
        data[index] = val;
        updateBIT(index, diff);
    }

    int sumRange(int left, int right) {
        return getSum(right) - getSum(left - 1);
    }

private:
    vector<int> data;
    vector<int> bit;

    void updateBIT(int index, int val) {
        index = index + 1;
        while (index < bit.size()) {
            bit[index] += val;
            index += index & -index;
        }
    }

    int getSum(int index) {
        int sum = 0;
        index = index + 1;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
};

                                            
class NumArray {
    private int[] nums;
    private int[] BIT;
    private int n;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.BIT = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            init(i, nums[i]);
        }
    }
    
    private void init(int i, int val) {
        i++;
        while (i <= n) {
            BIT[i] += val;
            i += i & -i;
        }
    }

    public void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        init(index, diff);
    }
    
    private int query(int i) {
        i++;
        int sum = 0;
        while (i > 0) {
            sum += BIT[i];
            i -= i & -i;
        }
        return sum;
    }
    
    public int sumRange(int left, int right) {
        return query(right) - query(left - 1);
    }
}

                                            
class NumArray(object):
    def __init__(self, nums):
        self.nums = nums
        self.prefix_sum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix_sum[i + 1] = self.prefix_sum[i] + nums[i]

    def update(self, index, val):
        diff = val - self.nums[index]
        self.nums[index] = val
        for i in range(index + 1, len(self.prefix_sum)):
            self.prefix_sum[i] += diff

    def sumRange(self, left, right):
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

                                            
public class NumArray {
    private int[] tree;
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.Length;
        tree = new int[n * 2];
        BuildTree(nums);
    }

    public void Update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        index += tree.Length / 2;
        tree[index] += diff;
        while (index > 0) {
            int left = index;
            int right = index;
            if (index % 2 == 0) {
                right = index + 1;
            } else {
                left = index - 1;
            }
            tree[index / 2] = tree[left] + tree[right];
            index /= 2;
        }
    }

    public int SumRange(int left, int right) {
        left += tree.Length / 2;
        right += tree.Length / 2;
        int sum = 0;
        while (left <= right) {
            if (left % 2 == 1) {
                sum += tree[left];
                left++;
            }
            if (right % 2 == 0) {
                sum += tree[right];
                right--;
            }
            left /= 2;
            right /= 2;
        }
        return sum;
    }

    private void BuildTree(int[] nums) {
        for (int i = 0; i < nums.Length; i++) {
            tree[nums.Length + i] = nums[i];
        }
        for (int i = nums.Length - 1; i > 0; i--) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }
}

To solve this coding challenge, the primary objective is to efficiently handle range sum queries and update operations on an array. A naive approach might use an array and recompute sums on each query which can be time-consuming especially when there are frequent updates. Instead, a more efficient solution involves using a prefix sum array to optimize the sum calculations.

Explanation

Our solution involves creating a class

NumArray

that handles two primary operations:

update(index, val) : Updates the value at a specific index.
sumRange(left, right) : Computes the sum of elements from the
left

index to the
right

index inclusive.

To make these operations efficient, we will:

Use a prefix sum array to store cumulative sums up to each index. This allows quick computation of any range sum.
Update both the original array and the prefix sum array whenever an update operation is performed.

Here's a detailed breakdown of how this approach can be implemented:

Detailed Steps in Pseudocode

Initialization

Initialize the
NumArray

object by passing the initial
nums

array.
Create a prefix sum array
prefix_sum

with a size of
len(nums) + 1

, initialized to zero.
Populate the
prefix_sum

array where each entry at index
i+1

contains the sum of elements in
nums

from the start to index
i

.

Update Operation

Calculate the difference between the new value and the current value at the specified index.
Update the original array
nums

at the specified index.
Propagate the change by updating the prefix sum array starting from the index + 1 to the end of the array, adding the calculated difference to each position.

Sum Range Operation

Use the prefix sum array to quickly calculate the sum from the
left

index to the
right

index by subtracting the cumulative sum up to
left

(exclusive) from the cumulative sum up to
right

(inclusive).

Pseudocode Implementation

                                            
class NumArray:
# Constructor to initialize object with given nums array
def __init__(nums):
# Store the original nums array
self.nums = nums
# Initialize prefix_sum array with zeros, length is len(nums) + 1
self.prefix_sum = [0] * (len(nums) + 1)

# Compute the prefix sums
for i from 0 to len(nums) - 1:
# Current prefix_sum at i+1 is sum of prefix_sum at i and nums at i
self.prefix_sum[i + 1] = self.prefix_sum[i] + nums[i]

# Method to update value at a specific index
def update(index, val):
# Compute the difference between the new value and the current value
difference = val - self.nums[index]
# Update the value in the nums array
self.nums[index] = val

# Update the prefix_sum array to reflect the change
for i from index + 1 to len(self.prefix_sum) - 1:
self.prefix_sum[i] += difference

# Method to return sum of elements from left index to right index
def sumRange(left, right):
# Return the difference between the prefix sum at right+1 and left
return self.prefix_sum[right + 1] - self.prefix_sum[left]

Step-by-Step Explanation

Initialization :

We start by storing the input
nums

array.
The
prefix_sum

array is initialized with an extra element (all zeros initially).
In a loop, we compute the prefix sums where each entry
prefix_sum[i + 1]

is the sum of all elements from the start up to
nums[i]

.

Update :

When updating an element at a given
index

, we first determine how much the value changes.
We update the element in the
nums

array.
We then update the rest of the
prefix_sum

array to reflect this change. Since the prefix sum represents cumulative sums, each entry from
index + 1

onwards will be incremented or decremented by the difference.

Sum Range :

To compute the sum of elements between two indices, we use the prefix sums. The sum of elements between indices
left

and
right

is given by
prefix_sum[right + 1] - prefix_sum[left]

. This operation is effectively constant time,
O(1)

.

This approach ensures that both update and sumRange operations are efficient, making the solution scalable for large inputs and frequent operations.