leetcode307

 1 class segTree:
 2     def __init__(self,nums):
 3         n = len(nums)
 4         for i in range(1,31):
 5             low,high = 2 ** (i-1),2 ** i
 6             if n > low and n < high:
 7                 fillzero = high - n
 8                 break
 9         self.sTree = [0] * 2 * n
10         for i in range(n,2*n):
11             self.sTree[i] = nums[i-n]
12         for i in range(n-1,0,-1):
13             self.sTree[i] = self.sTree[2*i] + self.sTree[2*i+1]
14             
15 class NumArray:
16     def __init__(self, nums: 'List[int]'):
17         self.segmentTree = segTree(nums)
18         self.n = len(nums)
19         
20 
21     def update(self, i: int, val: int) -> None:
22         i = i + self.n
23         self.segmentTree.sTree[i] = val
24         while i > 1:
25             i = i // 2
26             self.segmentTree.sTree[i] = self.segmentTree.sTree[2*i] + self.segmentTree.sTree[2*i+1]
27 
28     def sumRange(self, i: int, j: int) -> int:
29         left = i + self.n
30         right = j + self.n + 1
31         sums = 0
32         while left < right:
33             if left % 2 == 1:
34                 sums += self.segmentTree.sTree[left]
35                 left += 1
36             if right % 2 == 1:
37                 right -= 1
38                 sums += self.segmentTree.sTree[right]
39             left //= 2
40             right //= 2
41         return sums

算法思路：SegmentTree(线段树)。线段树是完全二叉树(不一定必须是满二叉树)。

线段树，查询操作时间复杂度O(logn)，更新操作时间复杂度O(logn)。