Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:


Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8


Note:


       The array is only modifiable by the update function.
       You may assume the number of calls to update and sumRange function is distributed evenly.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited

Starter code: class NumArray:
    def __init__(self, nums: List[int]):
    def update(self, i: int, val: int) -> None:
    def sumRange(self, i: int, j: int) -> int:
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

Solutions:
class NumArray:

	def __init__(self, nums):
		self.nums = nums
		self.step = 20
		self.cache = [0] * math.ceil(len(nums) / self.step)
		for i in range(len(nums)):
			self.cache[i // self.step] += nums[i]

	def update(self, i, val):
		old = self.nums[i]
		self.nums[i] = val
		self.cache[i // self.step] += val - old

	def sumRange(self, i, j):
		if j // self.step - i // self.step > 1:
			spliti = (i // self.step + 1) * self.step - 1
			splitj = j // self.step * self.step
			sumi = sum(self.nums[i:spliti + 1])
			sumj = sum(self.nums[splitj:j + 1])
			sumbetween = sum(self.cache[i // self.step + 1:j // self.step])
			return sumi + sumj + sumbetween
		else:
			return sum(self.nums[i:j + 1])


class NumArray:

	def __init__(self, nums):
		l = len(nums)
		self.nums = nums
		self.bit = [0] * (l + 1)
		for i in range(1, l + 1):
			self.update_delta(i, nums[i - 1])

	def update(self, i, val):
		bit = self.bit
		delta = val - self.nums[i]
		self.nums[i] = val
		self.update_delta(i + 1, delta)

	def sumRange(self, i, j):
		return self.get_sum(j + 1) - self.get_sum(i)

	def get_sum(self, i):
		bit = self.bit
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res

	def update_delta(self, i, delta):
		bit = self.bit
		l = len(bit)
		while i < l:
			bit[i] += delta
			i += i & -i


class NumArray:

	def __init__(self, nums):
		self.segTree = [0 for _ in range(len(nums) * 2)]
		self.build(nums)
		self.n = len(nums)

	def build(self, nums):
		n = len(nums)
		self.segTree[n:2 * n] = nums[:]
		for i in range(n - 1, 0, -1):
			self.segTree[i] = self.eval(self.segTree[2 * i], self.segTree[2 * i + 1])

	def eval(self, x1, x2):
		return x1 + x2

	def update(self, i, val):
		k = i + self.n
		delta = val - self.segTree[k]
		while k > 0:
			self.segTree[k] += delta
			k //= 2

	def sumRange(self, i, j):
		l = i + self.n
		r = j + self.n
		s = 0
		while l <= r:
			if l & 1 == 1:
				s += self.segTree[l]
				l += 1
			if r & 1 == 0:
				s += self.segTree[r]
			r -= 1
			l >>= 1
			r >>= 1
		return s