【leetcode】307. Range Sum Query

题目如下：

解题思路：就三个字-线段树。这个题目是线段树用法最经典的场景。

代码如下：

class NumArray(object):

    def __init__(self, nums):

        """

        :type nums: List[int]

        """

        self.nl = nums

        self.tree = []

        if len(nums) == 0:

            return

        for i in xrange((4*len(nums)+1)):

            self.tree.append([])

        self.build(1,len(nums),1,nums)

        #print self.tree

    def build(self,l,r,k,nums):

        self.tree[k] = [l,r]

        if l == r: #leaf

            self.tree[k].append(nums[l-1])

            return nums[l-1]

        wl = self.build(l,(l+r)/2,2*k,nums)

        wr = self.build((l+r)/2+1,r,2*k+1,nums)

        #print l,r,wl,wr

        self.tree[k].append(wl+wr)

        return self.tree[k][2]

    def update(self, i, val):

        """

        :type i: int

        :type val: int

        :rtype: void

        """

        if i > len(self.nl):

            return

        diff = self.nl[i] - val

        #for j in range(i,len(self.sl)):

        #    self.sl[j] -= diff

        self.nl[i] = val

        k = 1

        i += 1

        while True:

            self.tree[k][2] -= diff

            m = (self.tree[k][0] + self.tree[k][1])/2

            if self.tree[k][0] == self.tree[k][1]:

                break

            if i <= m:

                k = 2*k

            else:

                k = 2*k + 1

        #print self.tree

    def calcRange(self,i,j,k):

        #print i,j,k

        if i == self.tree[k][0] and j == self.tree[k][1]:

            return self.tree[k][2]

        m = (self.tree[k][0] + self.tree[k][1])/2

        if j <= m:

            return self.calcRange(i,j,2*k)

        elif i > m:

            return self.calcRange(i,j,2*k+1)

        else:

            return self.calcRange(i,m,2*k) + self.calcRange(m+1,j,2*k+1)

    def sumRange(self, i, j):

        """

        :type i: int

        :type j: int

        :rtype: int

        """

        #print self.sl

        #print self.nl

        return self.calcRange(i+1,j+1,1)

# Your NumArray object will be instantiated and called as such:

# obj = NumArray(nums)

# obj.update(i,val)

# param_2 = obj.sumRange(i,j)

巴特西

【leetcode】307. Range Sum Query - Mutable

最新文章

热门文章