In this guide, you will get 307. Range Sum Query – Mutable LeetCode Solution with the best time and space complexity. The solution to Range Sum Query – Mutable problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given an integer array nums, handle multiple queries of the following types:
Update the value of an element in nums.
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]).
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 104 calls will be made to update and sumRange.
307. Range Sum Query – Mutable LeetCode Solution in C++
class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}
void add(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}
int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private:
vector<int> sums;
static inline int lowbit(int i) {
return i & -i;
}
};
class NumArray {
public:
NumArray(vector<int>& nums) : nums(nums), tree(nums.size()) {
for (int i = 0; i < nums.size(); ++i)
tree.add(i + 1, nums[i]);
}
void update(int index, int val) {
tree.add(index + 1, val - nums[index]);
nums[index] = val;
}
int sumRange(int left, int right) {
return tree.get(right + 1) - tree.get(left);
}
private:
vector<int> nums;
FenwickTree tree;
}; /* code provided by PROGIEZ */
307. Range Sum Query – Mutable LeetCode Solution in Java
class FenwickTree {
public FenwickTree(int n) {
sums = new int[n + 1];
}
public void add(int i, int delta) {
while (i < sums.length) {
sums[i] += delta;
i += lowbit(i);
}
}
public int get(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
private int[] sums;
private static int lowbit(int i) {
return i & -i;
}
}
class NumArray {
public NumArray(int[] nums) {
this.nums = nums;
tree = new FenwickTree(nums.length);
for (int i = 0; i < nums.length; ++i)
tree.add(i + 1, nums[i]);
}
public void update(int index, int val) {
tree.add(index + 1, val - nums[index]);
nums[index] = val;
}
public int sumRange(int left, int right) {
return tree.get(right + 1) - tree.get(left);
}
private int[] nums;
private FenwickTree tree;
} // code provided by PROGIEZ
307. Range Sum Query – Mutable LeetCode Solution in Python
class FenwickTree:
def __init__(self, n: int):
self.sums = [0] * (n + 1)
def add(self, i: int, delta: int) -> None:
while i < len(self.sums):
self.sums[i] += delta
i += FenwickTree.lowbit(i)
def get(self, i: int) -> int:
summ = 0
while i > 0:
summ += self.sums[i]
i -= FenwickTree.lowbit(i)
return summ
@staticmethod
def lowbit(i: int) -> int:
return i & -i
class NumArray:
def __init__(self, nums: list[int]):
self.nums = nums
self.tree = FenwickTree(len(nums))
for i, num in enumerate(nums):
self.tree.add(i + 1, num)
def update(self, index: int, val: int) -> None:
self.tree.add(index + 1, val - self.nums[index])
self.nums[index] = val
def sumRange(self, left: int, right: int) -> int:
return self.tree.get(right + 1) - self.tree.get(left) # code by PROGIEZ
