303 range sum query - immutable
303. Range Sum Query - Immutable
题目： https://leetcode.com/problems/range-sum-query-immutable/
tag : DP 难度 : Easy
sum(i, j) = nums[i] j = i
sum(i,j) = sum[i,j-1] + nums[j] j > i
Python代码
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.sums = nums
for i in range(1, len(self.sums)):
self.sums[i] = self.sums[i-1] + self.sums[i]
def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
if i == 0 :
return self.sums[j]
else :
return self.sums[j] - self.sums[i-1]
