【LeetCode】307. 区域和检索 - 数组可修改
目录
- 描述
- Python
- 1. 线段树
- 2. 分块和
- 3. 树状数组
描述
给定一个数组nums，请完成两类查询。其中一类查询要求 更新 数组nums下标对应的值；另一类查询要求返回数组nums中索引left和索引right之间（ 包含 ）的nums元素的 和 ，其中left <= right
实现NumArray类：
NumArray(int[] nums)：用整数数组nums初始化对象void update(int index, int val)：将nums[index]的值 更新 为valint sumRange(int left, int right)：返回数组nums中索引left和索引right之间（ 包含 ）的nums元素的 和
Python
1. 线段树
class NumArray:
# 初始化
def __init__(self, nums: List[int]):
'''变量'''
n = len(nums) # 数组长度
'''属性'''
self.n = n # 长度
self.seg = [0] * (n * 4) # 线段树
# 在数组上构建线段树
self.build(nums, 0, 0, n - 1)
# 建树
def build(self, nums: List[int], node: int, s: int, e: int):
"""
nums:存入线段树的数组
node:线段树的结点下标，二叉树结点的左子结点下标为 node×2+1，右子结点下标为 node×2+2
s:指定区间左端点
e:指定区间右端点
"""
# 递归出口设为叶子结点，即区间为单值数组
if s == e:
self.seg[node] = nums[s]
return
# 区间中点
m = s + (e - s) // 2
# 递归调用，左右分化，直至到达出口
self.build(nums, node * 2 + 1, s, m)
self.build(nums, node * 2 + 2, m + 1, e)
# 进入出口后，执行计算队列，自下而上构建结点，结点存入子结点之和，即左右子区间之和
self.seg[node] = self.seg[node * 2 + 1] + self.seg[node * 2 + 2]
# 单点修改
def change(self, index: int, val: int, node: int, s: int, e: int):
"""
index:目标索引，即需要修改的元素的索引
val:修改的目标值
node:线段树的结点下标
s:数组全域左端点
e:数组全域右端点
"""
# 递归出口设为目标索引对应的叶子结点
if s == e:
self.seg[node] = val
return
# 区间中点
m = s + (e - s) // 2
# 递归调用，二分查找目标索引，直至到达出口
if index <= m:
self.change(index, val, node * 2 + 1, s, m)
else:
self.change(index, val, node * 2 + 2, m + 1, e)
# 进入出口后，执行计算队列，自下而上更新子结点和
self.seg[node] = self.seg[node * 2 + 1] + self.seg[node * 2 + 2]
# 范围求和
def range(self, left: int, right: int, node: int, s: int, e: int) -> int:
"""
left:目标区间左端点
right:目标区间右端点
node:线段树的结点下标
s:数组全域左端点
e:数组全域右端点
"""
# 匹配到目标区间，返回对应的结点
if left == s and right == e:
return self.seg[node]
# 区间中点
m = s + (e - s) // 2
# 递归调用，二分查找目标区间，直至到达出口
if right <= m:
return self.range(left, right, node * 2 + 1, s, m)
if left > m:
return self.range(left, right, node * 2 + 2, m + 1, e)
# 失配，返回子结点和
return self.range(left, m, node * 2 + 1, s, m) + self.range(m + 1, right, node * 2 + 2, m + 1, e)
# 将参数拓展后的函数放入测试接口
def update(self, index: int, val: int) -> None:
self.change(index, val, 0, 0, self.n - 1)
def sumRange(self, left: int, right: int) -> int:
return self.range(left, right, 0, 0, self.n - 1)
2. 分块和
class NumArray:
# 初始化
def __init__(self, nums: List[int]):
'''变量'''
n = len(nums) # 数组长度
size = int(n ** 0.5) # 子块长度：数组长度的二次方根
sums = [0] * ((n + size - 1) // size) # 分块和列表：子块数量 = n/size（向上取整）
# 枚举索引和值
for i, num in enumerate(nums):
sums[i // size] += num # 计算分块和
'''属性'''
self.nums = nums
self.size = size
self.sums = sums
# 单点修改
def update(self, index: int, val: int) -> None:
# 更新分块和
self.sums[index // self.size] += val - self.nums[index]
# 更新数组
self.nums[index] = val
# 范围求和
def sumRange(self, left: int, right: int) -> int:
# 子块长度
m = self.size
# 子块索引
b1, b2 = left // m, right // m
# 区间同块：暴力求和
if b1 == b2:
return sum(self.nums[left:right + 1])
# 区间不同块；分块和 + 首尾余项
return sum(self.nums[left:(b1 + 1) * m]) + sum(self.sums[b1 + 1:b2]) + sum(self.nums[b2 * m:right + 1])
3. 树状数组
class NumArray:
# 初始化
def __init__(self, nums: List[int]):
'''属性'''
self.nums = nums # 数组
self.tree = [0] * (len(nums) + 1) # 树：序列下标从1开始，结点0为空
# 枚举索引和值：索引从1开始
for i, num in enumerate(nums, 1):
self.add(i, num)
# 子类和
def add(self, index: int, val: int):
# 由叶子结点 i 向上追溯父节点 i+lowbit(i)，直至根节点
while index < len(self.tree):
self.tree[index] += val # nums[i]加入结点i，及其所有父类结点
index += index & -index # lowbit(i) = i&(~i+1) = i&(-i)
# 前缀和
def prefixSum(self, index) -> int:
# 和
s = 0
# 由当前节点 i 向上追溯索引差最小的低序结点 i-lowbit(i)，直至空结点
while index:
s += self.tree[index] # s 包括的结点下标包括 i+k*lowbit(i)
index &= index - 1 # i -= lowbit(i)
return s
# 单点修改
def update(self, index: int, val: int) -> None:
self.add(index + 1, val - self.nums[index]) # 先修改区间和，计算并补足差值
self.nums[index] = val # 再修改原数组
# 区间和
def sumRange(self, left: int, right: int) -> int:
# 前缀和之差
return self.prefixSum(right + 1) - self.prefixSum(left)