## 题目描述：

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```

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

## 题目大意：

1. 数组只能通过update函数修改。
2. 你可以假设update函数与sumRange函数的调用次数是均匀分布的。

## Python代码：

``````class NumArray(object):
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
self.size = size = len(nums)
h = int(math.ceil(math.log(size, 2))) if size else 0
maxSize = 2 ** (h + 1) - 1
self.st = [0] * maxSize
if size:
self.initST(0, size - 1, 0)

def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: int
"""
if i < 0 or i >= self.size:
return
diff = val - self.nums[i]
self.nums[i] = val
self.updateST(0, self.size - 1, i, diff, 0)

def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
if i < 0 or j < 0 or i >= self.size or j >= self.size:
return 0
return self.sumRangeST(0, self.size - 1, i, j, 0)

def initST(self, ss, se, si):
if ss == se:
self.st[si] = self.nums[ss]
else:
mid = (ss + se) / 2
self.st[si] = self.initST(ss, mid, si * 2 + 1) + \
self.initST(mid + 1, se, si * 2 + 2)
return self.st[si]

def updateST(self, ss, se, i, diff, si):
if i < ss or i > se:
return
self.st[si] += diff
if ss != se:
mid = (ss + se) / 2
self.updateST(ss, mid, i, diff, si * 2 + 1)
self.updateST(mid + 1, se, i, diff, si * 2 + 2)

def sumRangeST(self, ss, se, qs, qe, si):
if qs <= ss and qe >= se:
return self.st[si]
if se < qs or ss > qe:
return 0
mid = (ss + se) / 2
return self.sumRangeST(ss, mid, qs, qe, si * 2 + 1) + \
self.sumRangeST(mid + 1, se, qs, qe, si * 2 + 2)

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

## Python代码：

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

while x <= self.n:
self.sums[x] += val
x += self.lowbit(x)

def lowbit(self,x):
return x & -x

def sum(self,x):
res = 0
while x > 0:
res += self.sums[x]
x -= self.lowbit(x)
return res

def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: int
"""
self.add(i + 1, val - self.nums[i])
self.nums[i] = val

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

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

Pingbacks已关闭。