303. Range Sum Query - Immutable [easy] (Python)

最新推荐文章于 2022-02-12 16:49:20 发布

原创最新推荐文章于 2022-02-12 16:49:20 发布 · 3.1k 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#python #LeetCode

LeetCode 同时被 2 个专栏收录

90 篇文章

订阅专栏

LeetCode解题报告

90 篇文章

订阅专栏

本文介绍了LeetCode上的Range Sum Query Immutable问题的三种解决方案：预处理前缀和、使用树状数组(Binary Index Tree)和利用线段树(Segment Tree)，并提供了详细的代码实现。

题目链接

https://leetcode.com/problems/range-sum-query-immutable/

题目原文

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

Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:
You may assume that the array does not change.
There are many calls to sumRange function.

题目翻译

给定一个整数数组nums，求其下标i到j（i≤j，包括i和j）之间的所有元素的和。
比如，给定 nums = [-2, 0, 3, -5, 2, -1]：
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
注意：假设数组不会变化；sumRange函数会被调用非常多次。

思路方法

题目说明了该函数会被调用多次，所以应该对此作出优化。题目给了执行的例子：

# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.sumRange(1, 2)

经测试，每次调用sumRange都重新计算结果会导致超时。

思路一

在初始化的时候，将从第一个元素开始到当前位置的所有元素的和求出来，存放到数组sums中。那么每次求一个范围的和时，只要计算两个下标处和的差即可。

代码

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

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

思路二

求部分和的要求正好与树状数组（Binary Index Tree，BIT）的操作吻合，所以可以实现一个BIT来做这道题。不过，实际上题目说了数组不会变化，所以BIT的优势并没有完全发挥，BIT的更新和计算部分和的时间复杂度都是O(logn)。

代码

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

    def updateBIT(self, i, val):
        i += 1
        while i <= self.length:
            self.BIT[i] += val
            i += i & (-i)

    def getBITsum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & (-i)
        return res

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

思路三

这题还可以用线段树（SegmentTree）来解决，每次查询的复杂度也是O(logn)。

代码

class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        self.ST = SegmentTree(nums)

    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.ST.query(self.ST.root, i, j)

class Node(object):
    def __init__(self, start, end):
        self.left, self.right = None, None
        self.start, self.end, self.sum = start, end, 0

class SegmentTree(object):
    def __init__(self, vals):
        self.root = self.build(0, len(vals)-1, vals)

    def build(self, start, end, vals):
        if start > end:
            return None
        root = Node(start, end)
        if start != end:
            mid = start + (end - start) / 2
            root.left = self.build(start, mid, vals)
            root.right = self.build(mid+1, end, vals)
            root.sum = root.left.sum + root.right.sum
        else:
            root.sum = vals[start]
        return root

    def query(self, root, start, end):
        if not root or start > end:
            return 0
        if start <= root.start and end >= root.end:
            return root.sum
        mid = root.start + (root.end - root.start) / 2
        left_sum = right_sum = 0
        if start <= mid:
            if end > mid:
                left_sum = self.query(root.left, start, mid)
            else:
                left_sum = self.query(root.left, start, end)
        if end > mid:
            if start <= mid:
                right_sum = self.query(root.right, mid+1, end)
            else:
                right_sum = self.query(root.right, start, end)
        return left_sum + right_sum