Range Sum Query - Mutable · Interview Problem

Back to problems

Leetcode

range-sum-query-mutable

Medium

Arrays

Segment Tree

Binary Indexed Tree

Fenwick Tree

Range Sum Query - Mutable

Perform mutable range sum queries on an array with update and sum range operations.

Acceptance 100%

Start Practice Editorial

Problem Statement

Core description from the backend problem record.

Description

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

Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive. 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 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]).

Input Format

Initialization: An integer array nums. Operations: update(index, val) and sumRange(left, right).

Output Format

For sumRange operations, return the sum of specified range. For update operations, no return output.

Constraints

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

Examples

Sample cases returned by the problem API.

Example 1

Input

NumArray([1, 3, 5])
sumRange(0, 2)
update(1, 2)
sumRange(0, 2)

Output

9

(After sumRange(0, 2), output is 9)

(None for update)

8

(After update(1, 2), sumRange(0, 2) outputs 8)

Explanation

Initially, sumRange(0, 2) = 1 + 3 + 5 = 9. After updating index 1 from 3 to 2, the array becomes [1, 2, 5]. Now sumRange(0, 2) = 1 + 2 + 5 = 8.

Loading Preptin

Description

Input Format

Output Format

Constraints