三个月算法进阶--day81
目录
节点的度
子树的数量
线段树
范围查询，对数时间，二叉树
叶节点包含原始数据，非叶节点包含数组的一个子范围上的聚合信息
构建线段树（区域和）
自下而上
def buildTree(nums):
if nums:
self.n = len(nums)
self.tree = [0 for _ in range(self.n * 2)]
for i in range(self.n, self.n * 2):
self.tree[i] = nums[i - self.n]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
更新线段树
def update(pos, val):
pos += self.n
self.tree[pos] = val
while pos:
left, right = pos, pos
if pos % 2:
left = pos - 1
else:
right = pos + 1
self.tree[pos // 2] = self.tree[left] + self.tree[right]
pos //= 2
区域和检索
def sumRange(l, r):
l += self.n
r += self.n
sum = 0
while l <= r:
if l % 2:
sum += self.tree[l]
l += 1
if not r % 2:
sum += self.tree[r]
r -= 1
l //= 2
r //= 2
return sum
记录
leetcode第307题区域和检索-数组可修改
class NumArray:
def __init__(self, nums: List[int]):
self.n = len(nums)
self.tree = [0 for _ in range(self.n * 2)]
for i in range(self.n, self.n * 2):
self.tree[i] = nums[i - self.n]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]
def update(self, i: int, val: int) -> None:
i += self.n
self.tree[i] = val
while i:
left, right = i, i
if i % 2:
left = i - 1
else:
right = i + 1
self.tree[i // 2] = self.tree[left] + self.tree[right]
i //= 2
def sumRange(self, i: int, j: int) -> int:
i += self.n
j += self.n
sum = 0
while i <= j:
if i % 2:
sum += self.tree[i]
i += 1
if not j % 2:
sum += self.tree[j]
j -= 1
i //= 2
j //= 2
return sum