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

解题方法

naive方法

用一个array,然后查找sum都要O(n)的复杂度

Binary Indexed Tree

使用BIT的话，update和sumRange的复杂度都可以变为O(log MaxVal)

注意这一题有很多可以出bug的坑：

• 原本BIT定义的是add, 而不是直接update,所以我们在update的时候要算出 和原来值的diff（保存一个原来的nums array），然后再用原来的方法add
• 建立tree[]的时候应该从1 - length，所以index的对应问题也要注意
• 在一开始建立tree[]的时候, 应该将class内的nums的元素都初始为0
• read value的时候，要注意i, j的包含问题

Solution

class NumArray(object):
    def __init__(self, nums):
        length = len(nums)
        self.maxIdx = length
        self.nums = [0 for i in range(length)]
        self.tree = [0 for i in range(length+1)]
        for idx, num in enumerate(nums):
            self.update(idx, num)

    def lastBit(self, x):
        return x & (~(x-1))

    def read(self, i):
        result = 0
        while i:
            result += self.tree[i]
            i -= self.lastBit(i)
        return result

    def update(self, i, val):
        diff, self.nums[i] = val - self.nums[i], val # find diff, then update
        i += 1 # cause tree[] start from 1
        while i <= self.maxIdx:
            self.tree[i] += diff
            i += self.lastBit(i)

    def sumRange(self, i, j):
        sum_i = self.read(i) # not include nums[i], 读的时候是对于tree的i位，不加1
        sum_j_1 = self.read(j+1) # include nums[j]
        return sum_j_1 - sum_i

Reference