摘要
在很多业务场景中，数据不仅要查询区间和，还会被实时修改。比如商城的库存系统、在线游戏中的积分榜，甚至是股票价格的区间统计。LeetCode 第 307 题正是针对这种“可修改+可查询”场景设计的，它要求你设计一个数据结构支持快速更新数组中的某个位置，同时还能高效查询任意区间的和。
本篇文章我们使用 Swift 实现两种经典数据结构方案：树状数组（Fenwick Tree） 和 线段树，并提供可运行代码、思路分析和示例演示，帮助你真正掌握区间查询加更新的优化思路。
描述
题目的要求是这样的：
设计一个 NumArray 类，它支持：
- 初始化一个整数数组
nums； - 方法
update(index, val)用来修改数组中nums[index]的值； - 方法
sumRange(left, right)返回当前数组在[left, right]范围内所有元素的和。
数组长度可达 3*10^4，操作次数也最多如此，如果每次 sumRange 都遍历数组，效率会非常低。我们需要在支撑快速更新的前提下，实现常数或对数级别的查询。
题解答案（Swift 实现 – 树状数组版）
我们首先给出使用 树状数组（Fenwick Tree）实现的代码，结构简洁，运行高效：
import Foundation
class NumArray {
private var nums: [Int]
private var bit: [Int]
private let n: Int
init(_ nums: [Int]) {
self.nums = nums
n = nums.count
bit = Array(repeating: 0, count: n + 1)
for i in 0..<n {
initUpdate(i, nums[i])
}
}
private func initUpdate(_ idx: Int, _ val: Int) {
var i = idx + 1
while i <= n {
bit[i] += val
i += i & -i
}
}
func update(_ index: Int, _ val: Int) {
let diff = val - nums[index]
nums[index] = val
var i = index + 1
while i <= n {
bit[i] += diff
i += i & -i
}
}
private func prefixSum(_ idx: Int) -> Int {
var sum = 0
var i = idx + 1
while i > 0 {
sum += bit[i]
i -= i & -i
}
return sum
}
func sumRange(_ left: Int, _ right: Int) -> Int {
return prefixSum(right) - (left > 0 ? prefixSum(left - 1) : 0)
}
}
此外，如果更喜欢面向范围分治的思想，也可以用线段树实现。但本文重心放在 Fenwick Tree，代码更简洁高效。
题解代码分析
为什么选择树状数组？
树状数组适合支持两类操作：
- 对单点进行增量更新（
O(log n)）； - 查询前缀和（
O(log n)）。
正好满足“两类操作都频繁”的场景，比起每次重新累加数组快得多，且实现相比线段树要简单。
初始化和更新逻辑
- 初始化时，我们先清 BIT（全 0），然后通过
initUpdate方法把每个元素累加到 BIT 中； - 更新时，调整
nums[index]，并计算差值diff，然后用while根据 BIT 的结构逐级更新影响范围。
区间和查询
通过两个前缀和差值：
sumRange(l, r) = prefixSum(r) - prefixSum(l - 1)
其中 prefixSum(idx) 用标准的 BIT 查询方式累加相关节点即可。
示例测试及结果
我们可以建立几个测试用例，用来验证代码正确性：
let numArray = NumArray([1, 3, 5])
print(numArray.sumRange(0, 2)) // 输出 9
numArray.update(1, 2) // nums 变为 [1,2,5]
print(numArray.sumRange(0, 2)) // 输出 8
// 更多测试
let arr = NumArray([0,1,2,3,4])
print(arr.sumRange(1,3)) // 输出 6
arr.update(2, 10)
print(arr.sumRange(1,3)) // 输出 1+10+3=14
测试结果完全符合预期，并且执行速度非常快。
时间复杂度
- 初始化：构建 BIT 时为
O(n log n)； - 每次
update：O(log n)； - 每次
sumRange：两次前缀和查询，各O(log n)，总共O(log n)。
总操作次数 ≤ 3*10^4，logn 在数万量级下也在 15 左右，性能远超过暴力方法。
空间复杂度
- 存储原始数组
nums：O(n) - 存储 BIT 数组：
O(n + 1) - 总空间复杂度约为：O(n)
这非常适合内存充足的现代设备。
总结
- 树状数组 是解决“支持更新+快速求前缀和”类问题的高效工具；
- 通过巧妙利用二进制分段求和原理，实现每次查询
O(log n)； - 实际应用场景非常多，比如滑动窗口交易统计、用户访问计数、时序分析等；
- 如果你想处理更加复杂的区间更新或区间查询，也可以继续学习线段树、差分数组、BIT 范畴进阶。