leetcode Range Sum Query - Mutable

leetcode Range Sum Query - Mutable

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:

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

题目地址 ： leetcode Range Sum Query - Mutable

题意：

给定一个数组，让你正确实现如下两种操作:

• update(i , val )：让下标为i增加val
• sumRange(i，j): 计算数组从i到j的值

 

思路：

其实在 leetcode Range Sum Query – Immutable 我已经给多可变数组的解法。

直接上fenwick tree或者线段树都行。

fenwick tree比较好写，水水的1A~

关于fenwick tree看这里：  Fenwick tree (binary indexed tree)

Code

class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        self.sum_array = [0] * (len(nums) + 1)
        self.nums = nums
        self.n = len(nums)
        for i in xrange(len(nums)):
            self.add(i + 1,nums[i])

    def add(self,x,val):
        while x <= self.n:
            self.sum_array[x] += val
            x += self.lowbit(x)

    def lowbit(self,x):
        return x & -x

    def sum(self,x):
        res = 0
        while x >0:
            res += self.sum_array[x]
            x -= self.lowbit(x)
        return res

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: int
        """
        self.add(i + 1, val - self.nums[i])
        self.nums[i] = val

    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        if not self.nums: return  0
        return self.sum(j+1) - self.sum(i)