LeetCode 307. 区域和检索 - 数组可修改

2020-10-24 HGNULB 约 14 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 307. 区域和检索 - 数组可修改

题意分析

设计一个类 NumArray，用一个整数数组初始化，之后要支持两种操作交替、任意次数地调用：update(index, val) 把某个位置的值改成 val（注意是赋值不是增量），sumRange(left, right) 返回闭区间 [left, right] 的元素和。

这是一道设计题，考的不是算出某个答案，而是在两种操作之间做复杂度权衡。所以先把两种极端方案摆出来：直接存原数组，update 是 $O(1)$ 但 sumRange 要遍历区间，是 $O(n)$；预处理前缀和数组，sumRange 是 $O(1)$ 但 update 要重算后面所有前缀，是 $O(n)$。两种方案都有一侧是 $O(n)$。

数据规模是决定性信号：数组长度和调用次数都到 $3 \times 10^4$ 量级。若某一侧是 $O(n)$，最坏情况是 $3 \times 10^4 \times 3 \times 10^4 = 9 \times 10^8$ 次操作，超时。所以必须找一个两边都是 $O(\log n)$ 的折中方案。

「单点修改 + 区间求和 + 两边都要 $\log$」这三条合起来，几乎是树状数组（Fenwick Tree）或线段树的定义式描述。两者都可以，树状数组代码短得多、常数更小，是本题的首选。

还有一个容易被忽略的细节：update 传入的是新值而不是增量。而树状数组的原生操作是「给某个位置加上一个增量」，所以必须自己维护一份原数组副本，用 新值 - 旧值 算出增量，再把增量喂给树状数组，同时更新副本。这份副本不是可有可无的辅助，而是接口语义决定的必需品。

边界：sumRange(0, r) 时需要 prefix(-1)，必须让它返回 0 而不是越界；left == right 时区间只有一个元素；update 成相同的值时增量为 0，应当能正确地什么都不改变；数组元素可以为负，所以不能假设前缀和单调。

解法：树状数组（Fenwick）

核心思路

先看两个朴素方案为什么不够。存原数组时，sumRange(0, n-1) 要累加 $n$ 项；存前缀和时，update(0, x) 要修正 $n$ 个前缀。瓶颈的本质是：这两种存储都把「区间和」这件事表达得过于极端——要么完全不预聚合（查询慢），要么把每个前缀都完整预聚合（更新时牵一发动全身）。

关键观察是：区间和满足结合律，任何一段和都可以由若干不重叠的子段和拼出来。如果我们预先算好的不是「每个前缀」而是「一批精心挑选的子段」，让它们既能拼出任意前缀，又能保证单个元素只出现在少数几个子段里，那么查询和更新就能同时变快。

树状数组给出的就是这样一组子段。它把长度为 $n$ 的数组配上一个 1-based 的辅助数组 bit，规定 bit[i] 保存的是原数组中区间 $(i - \mathrm{lowbit}(i),\ i]$ 的和，其中 $\mathrm{lowbit}(i) = i \& (-i)$ 是 $i$ 的二进制最低位 1 所代表的值。举例：bit[4] 的 lowbit 是 4，管辖 $(0, 4]$ 即前 4 个元素；bit[6] 的 lowbit 是 2，管辖 $(4, 6]$ 即第 5、6 两个元素；bit[7] 的 lowbit 是 1，只管辖第 7 个元素。

这个定义就是树状数组的不变量，所有操作都围绕它维持。之所以选 lowbit 作为管辖长度，是因为它让两个方向的跳跃都恰好对应二进制位的增减：

求前缀和：要算 $[1, i]$ 的和，先取 bit[i]（覆盖 $(i - \mathrm{lowbit}(i), i]$），剩下的部分是 $[1, i - \mathrm{lowbit}(i)]$，于是令 i -= lowbit(i) 继续累加。每次减掉最低位的 1，二进制中 1 的个数至少减少一个，所以最多循环 $O(\log n)$ 次。

单点加增量：位置 $i$ 被哪些 bit[j] 管辖？答案是 j = i，然后 j += lowbit(j) 一路向上，直到超出数组范围。每次加最低位的 1 会让这一位进位，同样最多 $O(\log n)$ 步。这两个方向一个减 lowbit 一个加 lowbit，是树状数组最容易记混的地方，记法是「查询往回缩、更新往前推」。

有了 $O(\log n)$ 的前缀和，区间和就是两个前缀和之差：sumRange(l, r) = prefix(r) - prefix(l-1)。这里必须约定 prefix(-1) = 0，代表空前缀。

最后处理接口的语义差。update 给的是新值，树状数组只会加增量，所以类里额外维护一份 nums 副本：delta = val - nums[index]，先算增量，再更新副本，再把 delta 推进树状数组。构造函数则把副本初始化为全 0，然后对每个位置调用一次 update(i, nums[i])，让增量恰好等于原值，从而把整棵树建起来。

下标要小心：树状数组内部必须是 1-based（因为 $\mathrm{lowbit}(0) = 0$，从 0 出发会死循环），而题目接口是 0-based。所以 bit 数组开 n + 1 长度，所有进出都做 +1 / -1 的转换，转换点集中在 add 和 prefix 两个私有方法里，外部接口保持 0-based 不变。

解题步骤

成员变量设计：nums 保存当前值的副本、bit 保存树状数组，长度为 n + 1。为什么必须有 nums 副本——接口的 update 传新值而树状数组只接受增量，没有副本就算不出 delta；为什么 bit 要多开一位——树状数组是 1-based，下标 0 空置不用。

构造函数把 nums 初始化为全 0，再逐个调用 update(i, nums[i])：为什么初值必须是 0——这样 delta = nums[i] - 0 = nums[i]，一次 update 就等价于「把第 i 个元素从无到有加进树里」；若直接把副本填成原值，delta 会算成 0，树状数组全是 0，所有查询返回 0。

add(index, delta)：令 i = index + 1，循环 while (i < bit.length)，执行 bit[i] += delta 后 i += i & -i：为什么向上跳是加 lowbit——位置 index 被所有「管辖区间包含它」的节点覆盖，这些节点的下标恰好由不断加 lowbit 生成；为什么循环条件是 i < bit.length 而不是 i <= n——两者等价（bit.length == n + 1），写成前者更不易错。

prefix(index)：index < 0 时返回 0；否则令 i = index + 1，循环 while (i > 0)，累加 bit[i] 后 i -= i & -i：为什么向下跳是减 lowbit——bit[i] 覆盖了 $(i - \mathrm{lowbit}(i), i]$，剩余部分的右端点正是 i - lowbit(i)；为什么必须先判 index < 0——sumRange(0, r) 会调用 prefix(-1)，此时 i = 0，若不提前返回，循环条件 i > 0 恰好也不成立而返回 0，本例侥幸正确，但显式判断能让意图清晰，也能防住某些实现里 i 变成负数的情况。

update(index, val)：先算 delta = val - nums[index]，再写 nums[index] = val，最后 add(index, delta)：为什么顺序不能变——delta 依赖旧值，先覆盖 nums[index] 会让 delta 恒为 0，树状数组永远不更新。

sumRange(left, right) 返回 prefix(right) - prefix(left - 1)：为什么减的是 left - 1 而不是 left——前缀和是闭区间 $[0, i]$ 的和，要得到 $[left, right]$ 必须扣掉 $[0, left-1]$；减 left 会把 nums[left] 也扣掉。

以 nums = [1, 3, 5] 走一遍。n = 3，bit 长度为 4，初值 bit = [0,0,0,0]，副本 nums = [0,0,0]。

构造阶段。
update(0, 1)：delta = 1 - 0 = 1，副本变成 [1,0,0]。add(0, 1)：i = 1，bit[1] += 1 得 1；lowbit(1) = 1，i 变成 2，bit[2] += 1 得 1；lowbit(2) = 2，i 变成 4，不小于 bit.length = 4，停止。此时 bit = [0,1,1,0]。
update(1, 3)：delta = 3 - 0 = 3，副本 [1,3,0]。add(1, 3)：i = 2，bit[2] += 3 得 4；i 变成 4，停止。bit = [0,1,4,0]。
update(2, 5)：delta = 5，副本 [1,3,5]。add(2, 5)：i = 3，bit[3] += 5 得 5；lowbit(3) = 1，i 变成 4，停止。bit = [0,1,4,5]。

核对不变量：bit[1] 管辖 $(0,1]$ 即 nums[0] = 1，值为 1，✓；bit[2] 管辖 $(0,2]$ 即 nums[0]+nums[1] = 4，值为 4，✓；bit[3] 管辖 $(2,3]$ 即 nums[2] = 5，值为 5，✓。

sumRange(0, 2)：prefix(2) - prefix(-1)。prefix(-1) 因 index < 0 返回 0。prefix(2)：i = 3，累加 bit[3] = 5，res = 5；lowbit(3) = 1，i 变成 2，累加 bit[2] = 4，res = 9；lowbit(2) = 2，i 变成 0，循环结束，返回 9。所以结果是 9 - 0 = 9，即 $1+3+5$，正确。注意这次查询只访问了两个节点而不是三个元素，跳跃路径 $3 \to 2 \to 0$ 正是不断减 lowbit 的结果。

update(1, 2)：delta = 2 - nums[1] = 2 - 3 = -1，副本变成 [1,2,5]。add(1, -1)：i = 2，bit[2] += -1 得 3；i 变成 4，停止。bit = [0,1,3,5]。注意只改了一个节点——位置 1 只被 bit[2] 管辖，bit[1] 和 bit[3] 都不含它，所以不必改动。

再次 sumRange(0, 2)：prefix(2) 走 $3 \to 2$，累加 5 + 3 = 8，减去 0 得 8，即 $1+2+5$，正确。

sumRange(1, 2)：prefix(2) - prefix(0)。prefix(2) = 8。prefix(0)：i = 1，累加 bit[1] = 1，res = 1；lowbit(1) = 1，i 变成 0，结束，返回 1。结果 8 - 1 = 7，即 $2 + 5$，正确。这里 prefix(0) 返回的是 nums[0] 而不是 0，正是 left - 1 这个减一存在的意义。

最后看一个容易出错的调用 update(1, 2) 再调用一次同样的 update(1, 2)：第二次 delta = 2 - 2 = 0，add 会把 0 加到路径上的节点，等于什么都没变，bit 保持 [0,1,3,5]，行为正确。

代码实现

// 维护 bit 存前缀增量，update 用差值更新。
class NumArray {
    private int[] nums;
    private int[] bit;

    public NumArray(int[] nums) {
        this.nums = new int[nums.length];
        this.bit = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            update(i, nums[i]);
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        add(index, delta);
    }

    public int sumRange(int left, int right) {
        return prefix(right) - prefix(left - 1);
    }

    private void add(int index, int delta) {
        int i = index + 1;
        while (i < bit.length) {
            bit[i] += delta;
            i += i & -i;
        }
    }

    private int prefix(int index) {
        if (index < 0) {
            return 0;
        }
        int res = 0;
        int i = index + 1;
        while (i > 0) {
            res += bit[i];
            i -= i & -i;
        }
        return res;
    }
}

// 维护 bit 存前缀增量，update 用差值更新。
type NumArray struct {
	nums []int
	bit  []int
}

func Constructor(nums []int) NumArray {
	na := NumArray{nums: make([]int, len(nums)), bit: make([]int, len(nums)+1)}
	for i := 0; i < len(nums); i++ {
		na.Update(i, nums[i])
	}
	return na
}

func (this *NumArray) Update(index int, val int) {
	delta := val - this.nums[index]
	this.nums[index] = val
	i := index + 1
	for i < len(this.bit) {
		this.bit[i] += delta
		i += i & -i
	}
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.prefix(right) - this.prefix(left-1)
}

func (this *NumArray) prefix(index int) int {
	if index < 0 {
		return 0
	}
	res := 0
	i := index + 1
	for i > 0 {
		res += this.bit[i]
		i -= i & -i
	}
	return res
}

复杂度分析

时间复杂度：构造 $O(n \log n)$，update 与 sumRange 均为 $O(\log n)$。add 每次执行 i += lowbit(i)，把当前位置的贡献传给下一个更大的管辖节点；一条祖先链长度不超过下标的二进制位数。prefix 每次执行 i -= lowbit(i)，消掉一个最低位 1，同样至多走 $O(\log n)$ 步。构造函数调用 $n$ 次 update；若需要，可用线性建树降为 $O(n)$，但不影响两种在线操作。

空间复杂度：$O(n)$。凭什么：bit 数组长度是 $n + 1$，nums 副本长度是 $n$，两者都是线性的；所有操作都是迭代实现，没有递归栈。相比线段树的 $4n$ 数组，树状数组的常数明显更小，这也是本题选它的原因之一。

关键点总结

设计题要先把极端方案的复杂度摆出来，说明为什么 $O(1)$ 查询配 $O(n)$ 更新和反过来都不可接受，再引出 $O(\log n)$ 的折中。直接甩出「用树状数组」而讲不清动机，是面试里最常见的减分点。

树状数组的全部内容就是一条不变量：bit[i] 保存原数组 $(i - \mathrm{lowbit}(i),\ i]$ 的和。查询和更新的跳跃规则都是这条不变量的推论，记住它比背两个循环靠谱得多。

方向别记反：查询往回缩（i -= lowbit(i)），更新往前推（i += lowbit(i)）。可以用「查询是在拆分前缀、更新是在通知祖先」来理解。

树状数组必须 1-based，因为 $\mathrm{lowbit}(0) = 0$ 会让两个循环都卡死。把下标转换集中在 add / prefix 两个私有方法里，对外保持题目的 0-based 接口，是干净的分层写法。

当接口给的是「设为新值」而底层结构只支持「加增量」时，必须额外维护一份当前值副本来做差。这是适配器思维，在线段树、差分数组、并查集带权等场景里反复出现。

区间和拆成两个前缀和之差时，减的一定是 left - 1 而不是 left，并且要为 left == 0 约定 prefix(-1) = 0。这两处是前缀和类题目的固定检查点。

面试视角：这题的标准答法是先讲清权衡动机，再给出树状数组并解释 lowbit 的含义，最后主动分析两个循环各自为什么是 $O(\log n)$。被问「线段树呢」时要能说出：线段树更通用（支持区间修改、区间最值等非可减信息），但代码长、常数大；本题只需单点改和区间和，树状数组更合适。

面试视角：常见追问是「如果要支持区间修改、单点查询呢」。要能立刻答出把树状数组建在差分数组上——区间 $[l, r]$ 加 v 等价于差分数组上 add(l, v) 和 add(r+1, -v)，单点查询变成求差分的前缀和；再进一步「区间修改 + 区间查询」则需要维护两个树状数组。

易错点总结

update 里把 val 当增量直接 add(index, val)：用例先 update(1, 3) 再 update(1, 2)，正确结果应是位置 1 变成 2，而这种写法会让它变成 $3 + 2 = 5$，sumRange(1,1) 返回 5 而不是 2。

update 里先写 nums[index] = val 再算 delta：用例 update(1, 2) 当原值是 3 时，delta 变成 $2 - 2 = 0$，树状数组完全不更新，sumRange(0,2) 仍返回 9 而正确答案是 8。

构造函数把 this.nums 直接初始化成传入的数组再逐个 update：用例 nums = [1,3,5]，每次 delta = nums[i] - nums[i] = 0，bit 全为 0，任何 sumRange 都返回 0。

sumRange 写成 prefix(right) - prefix(left)：用例 nums = [1,3,5]、sumRange(1,2)，会算成 $9 - 4 = 5$，而正确答案是 $3+5=8$；nums[left] 被错误扣除。

prefix 没有处理 index < 0：用例 sumRange(0, 2)，prefix(-1) 时 i = 0，若循环条件写成 i >= 0 则 bit[0] 会被累加且 lowbit(0) = 0 导致 i 永远不变，陷入死循环。

树状数组用 0-based（bit 长度取 n，i = index）：用例 update(0, 5)，i = 0 时 lowbit(0) = 0，i += 0 让循环永远停不下来，程序挂死。

add 的跳跃方向写成 i -= i & -i：用例 nums = [1,3,5]，构造时 update(2,5) 会从 i=3 跳到 i=2 再到 i=0，把 5 加到了 bit[2] 上，破坏不变量；随后 sumRange(0,0) 会返回错误的值。

prefix 的跳跃方向写成 i += i & -i：用例 prefix(2)，i 从 3 跳到 4、8、16…… 越界或死循环，取决于循环条件。

add 的循环条件写成 i <= n 却把 n 取成了 bit.length：用例 nums = [1,3,5]（bit.length = 4），i = 4 时会执行 bit[4] += delta 直接越界。

lowbit 写成 i & (i - 1)：用例 i = 6，6 & 5 = 4 而正确的 lowbit(6) = 6 & -6 = 2；i & (i-1) 是「消掉最低位 1」而不是「取出最低位 1」，两者含义完全不同，会让跳跃路径全错。

不保存原值，误把 bit[index+1] 当成该位置当前值来算差量：nums = [1,3] 时 bit[2] 保存的是前两项之和 4，不是 nums[1] = 3；把下标 1 更新为 2 会算出错误差量 2-4=-2，区间和变成 2 而不是 3。

数组元素为负时假设前缀和单调而想用二分：用例 nums = [5, -3, 5]，prefix 序列是 5, 2, 7 非单调，任何依赖单调性的优化都会出错；树状数组本身不需要这个假设，但衍生用法（如求第 k 小）需要值域非负，要说清适用前提。

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	没有修改操作，直接前缀和即可，用来对照理解修改需求如何逼出树状数组
308. 二维区域和检索 - 矩阵可修改	中等	把树状数组升到二维，两个方向各跳一次 lowbit，区间和要用容斥拆成四个前缀
315. 计算右侧小于当前元素的个数	困难	把树状数组建在值域上做计数而非求和，需要先离散化
327. 区间和的个数	困难	前缀和 + 树状数组统计落在区间内的历史前缀个数，考察问题到值域计数的转化
493. 翻转对	困难	同为值域树状数组计数，但比较条件带系数，离散化时要把 $2 \times nums[i]$ 也放进值域
732. 我的日程安排表 III	困难	需要区间修改 + 全局最值，树状数组不再适用，必须换动态开点线段树
218. 天际线问题	困难	同属「动态维护聚合量」，但聚合的是最大值且要支持删除，指向多重集合或线段树