当前位置：首页 > news >正文

Swift 解锁数组可修改场景：LeetCode 307 高效解法全解析

news 2025/7/12 10:41:29

在这里插入图片描述

文章目录

- 摘要
- 描述
- 题解答案（Swift 实现 – 树状数组版）
- 题解代码分析
- - 为什么选择树状数组？
  - 初始化和更新逻辑
  - 区间和查询
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结

摘要

在很多业务场景中，数据不仅要查询区间和，还会被实时修改。比如商城的库存系统、在线游戏中的积分榜，甚至是股票价格的区间统计。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 Foundationclass NumArray {private var nums: [Int]private var bit: [Int]private let n: Intinit(_ nums: [Int]) {self.nums = numsn = nums.countbit = 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 + 1while i <= n {bit[i] += vali += i & -i}}func update(_ index: Int, _ val: Int) {let diff = val - nums[index]nums[index] = valvar i = index + 1while i <= n {bit[i] += diffi += i & -i}}private func prefixSum(_ idx: Int) -> Int {var sum = 0var i = idx + 1while 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