1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class NumArray(object):
def lowbit(self,x):
# -x 是x的补码，按位取反，然后加1
return x&-x
def add(self, x, val):
while x<= self.n:
self.sums[x] += val
x+= self.lowbit(x)
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.nums = nums
self.sums = [0] * (len(nums)+1)
self.n = len(nums)
for i in range(len(nums)):
self.add(i+1, nums[i])
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
"""
# update sums and nums
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:
if __name__ == "__main__":
numArray = NumArray([1,3,5])
numArray.sumRange(0, 1)
numArray.update(1, 10)
numArray.sumRange(1, 2)
|