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:
- 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]).
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); }
0 Comments