For beginners, here is my summary about this problem(experience+reference, in Python)

  • 0
    1. Firstly, I try to solve this in a naive way: (1) use an array, and scan from i to j when sum or (2) use an accumulating array to store the sum so far. TLE of course, you know O(n)+O(1) or O(1)+n(n)...

    2. Then i tried segment tree (for the first time), it works~ looks like this:

    class SegmentTreeNode(object):
        def __init__(self, val=None, left_node=None, right_node=None, left_bound=None, right_bound=None):
            self.val = val
            self.left_node = left_node
            self.right_node = right_node
            self.left_bound = left_bound
            self.right_bound = right_bound
    class NumArray(object):
        def construct_segment_tree(self, nums, l, r):
            #1. exit
            if l==r-1:
                leave_node = SegmentTreeNode(nums[l], None, None, l, r)
                return leave_node
            #2. general
            mid = (l+r)/2
            right_subtree = self.construct_segment_tree(nums, mid, r)
            left_subtree = self.construct_segment_tree(nums, l, mid)
            root = SegmentTreeNode(right_subtree.val+left_subtree.val, left_subtree, right_subtree, l, r)
            return root
        def __init__(self, nums):
            if len(nums)==0:
                self.segment_tree_root = None
            self.segment_tree_root = self.construct_segment_tree(nums, 0, len(nums))
        def update_core(self, root, i, val):
            #1. exit
            if root.left_bound==root.right_bound-1:
                diff = val-root.val
                root.val += diff
                return diff
            #2. general
            mid = (root.left_bound+root.right_bound)/2
            if i<mid:
                diff = self.update_core(root.left_node, i, val)
                diff = self.update_core(root.right_node, i, val)
            root.val += diff
            return diff
        def update(self, i, val):
            self.update_core(self.segment_tree_root, i, val)
        def sumRange_core(self, root, i, j):
            if root==None or j<=root.left_bound or i>=root.right_bound:
                return 0
            #if i==root.left_bound and j==root.right_bound:
            if i<=root.left_bound and root.right_bound<=j:
                return root.val
            #2. general
            return self.sumRange_core(root.left_node, i, j)+self.sumRange_core(root.right_node, i, j)
        def sumRange(self, i, j):
            return self.sumRange_core(self.segment_tree_root, i, j+1)

    Not elegant enough and the time is about 600ms...

    1. So i tried Binary Indexed Tree, and got 148ms, as following:
    class NumArray(object):
        def __init__(self, nums):
            self.n = len(nums)
            self.a, self.c = nums, [0] * (self.n + 1)
            for i in range(self.n):
                k = i + 1
                while k <= self.n:
                    self.c[k] += nums[i]
                    k += (k & -k)
        def update(self, i, val):
            diff, self.a[i] = val - self.a[i], val
            i += 1
            while i <= self.n:
                self.c[i] += diff
                i += (i & -i)
        def sumRange(self, i, j):
            res, j = 0, j + 1
            while j:
                res += self.c[j]
                j -= (j & -j)
            while i:
                res -= self.c[i]
                i -= (i & -i)
            return res

    Note: It is same with segment tree logically, but more elegant and concise and FAST~!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.