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]).

hackerrank Range Sum Query - Mutable problem solution


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);
}