Leetcode Range Sum Query - Mutable problem solution

In this Leetcode Range Sum Query - Mutable problem solution we have 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:

1. NumArray(int[] nums) Initializes the object with the integer array nums.
2. void update(int index, int val) Updates the value of nums[index] to be val.
3. 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]).

Problem solution in Python.

class NumArray(object):
def __init__(self, nums):
self.nums = nums
self.accu = [0]
self.diff = [0] * len(nums)
for num in nums:
self.accu += self.accu[-1] + num,

def update(self, i, nval):
oval, self.nums[i] = self.nums[i], nval
self.diff[i] += nval-oval

def sumRange(self, i, j):
return self.accu[j + 1] - self.accu[i] + sum(self.diff[i:j+1])

Problem solution in Java.

class Solution {
int[] prefix;
public NumArray(int[] nums) {
this.prefix = new int[nums.length + 1];
int temp = 0;
for(int i = 0; i < nums.length; i++){
temp += nums[i];
prefix[i + 1] = temp;
}
}

public void update(int i, int val) {
int before = prefix[i + 1] - prefix[i];
if(val > before){
for(int j = i + 1; j < prefix.length; j++){
prefix[j] += (val - before);
}
} else {
for(int j = i + 1; j < prefix.length; j++){
prefix[j] -= (before - val);
}
}
}

public int sumRange(int i, int j) {
return prefix[j + 1] - prefix[i];
}

private void print1D(int[] x) {
System.out.print("|");
for(int y: x) {
System.out.print(y + "|");
}
System.out.println();
}
}

Problem solution in C++.

class NumArray {
public:
NumArray(vector<int>& nums)
: Nums(std::move(nums))
{}

void update(int i, int val) {
Nums[i] = val;
}

int sumRange(int i, int j) {
return std::accumulate(Nums.begin() + i, Nums.begin() + j + 1, 0, std::plus<>());
}

private:
vector<int> Nums;
};

Problem solution in C.

#define MAXN    100000

typedef struct {
int tree[MAXN];
int num[MAXN];
int size;
} NumArray;

void build(NumArray *na, int node, int a, int b) {
if (a>b) {
return;
}
if (a==b) {
na->tree[node] = na->num[b];
return;
}
int left = 2*node+1, right = 2*node+2;
build(na, left, a, (a+b)/2);
build(na, right, (a+b)/2+1, b);
na->tree[node] = na->tree[left] + na->tree[right];
}

NumArray* numArrayCreate(int* nums, int numsSize) {
NumArray *na = (NumArray*)malloc(sizeof(NumArray));

for (int i=0; i<numsSize; i++) {
na->tree[i] = nums[i];

na->num[i] = nums[i];
}

na->size = numsSize;
build(na, 0,  0, numsSize-1);
return na;
}

void numArrayUpdate(NumArray* obj, int i, int val) {
int pos = i+obj->size;
obj->num[i] = val;
obj->tree[pos] = val;

int l, r, p;
while (pos>0) {
l=r=pos;
if (pos%2==0) { // right leaf if idx from zero
l=pos-1;
p = (pos-2)/2;
}
else {
r=pos+1;
p=(pos-1)/2;
}
obj->tree[p] = obj->tree[l] + obj->tree[r];
pos/=2;
}
}

int numArraySumRange(NumArray* obj, int i, int j) {
if(i>j) return -1000;
if(i==j) return obj->num[i];
int a = numArraySumRange(obj, i, (i+j)/2);
int b = numArraySumRange(obj, (i+j)/2+1, j);
return a+b;
}

void numArrayFree(NumArray* obj) {
free(obj);
}