LeetCode 第307题：区域和检索 - 数组可修改

📖 文章摘要

本文详细解析LeetCode第307题“区域和检索 - 数组可修改”，这是一道考察数据结构设计的中等难度题目。文章提供了多种解法，包括暴力法、分块处理、树状数组和线段树四种实现方案，并详细分析了它们的优劣。适合想要深入理解高级数据结构的程序员。

核心知识点： 树状数组、线段树、分块处理、区间查询
难度等级： 中等
推荐人群： 对数据结构设计感兴趣的程序员

题目描述

给你一个数组 nums，请你完成两类查询：

1. 更新 数组 nums 下标对应的值
2. 返回数组 nums 中索引 left 和 right 之间的和（包含 left 和 right）

实现 NumArray 类：

• NumArray(int[] nums) 用整数数组 nums 初始化对象
• void update(int index, int val) 将 nums[index] 的值更新为 val
• int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的和（包含 left 和 right）

示例

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示

• 1 <= nums.length <= 3 * 10⁴
• -100 <= nums[i] <= 100
• 0 <= index < nums.length
• -100 <= val <= 100
• 0 <= left <= right < nums.length
• 最多调用 3 * 10⁴ 次 update 和 sumRange 方法

解题思路

这道题有四种主要的解法，从简单到复杂依次是：

1. 暴力法
2. 分块处理
3. 树状数组（Binary Indexed Tree）
4. 线段树（Segment Tree）

每种方法都有其特点和适用场景，我们将详细分析每种方法的实现和性能特点。

图解思路

方法对比分析表

方法	更新操作复杂度	查询操作复杂度	空间复杂度	实现难度
暴力法	O(1)	O(n)	O(n)	简单
分块处理	O(1)	O(√n)	O(√n)	中等
树状数组	O(logn)	O(logn)	O(n)	中等
线段树	O(logn)	O(logn)	O(n)	困难

树状数组结构示意

节点索引	覆盖范围	计算方式	父节点
1	[0,0]	A[0]	2
2	[0,1]	A[0]+A[1]	4
3	[2,2]	A[2]	4
4	[0,3]	A[0]+A[1]+A[2]+A[3]	8

代码实现

方法一：暴力法（C#实现）

public class NumArray {
    private int[] nums;
    
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public void Update(int index, int val) {
        nums[index] = val;
    }
    
    public int SumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

方法二：分块处理（Python实现）

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
        n = len(nums)
        self.block_size = int(n ** 0.5)
        self.blocks = [0] * ((n + self.block_size - 1) // self.block_size)
        for i in range(n):
            self.blocks[i // self.block_size] += nums[i]
            
    def update(self, index: int, val: int) -> None:
        block_idx = index // self.block_size
        self.blocks[block_idx] += val - self.nums[index]
        self.nums[index] = val
        
    def sumRange(self, left: int, right: int) -> int:
        start_block = left // self.block_size
        end_block = right // self.block_size
        
        if start_block == end_block:
            return sum(self.nums[left:right+1])
            
        sum_val = sum(self.nums[left:(start_block + 1) * self.block_size])
        sum_val += sum(self.blocks[start_block+1:end_block])
        sum_val += sum(self.nums[end_block * self.block_size:right+1])
        
        return sum_val

方法三：树状数组（C++实现）

class NumArray {
private:
    vector<int> nums;
    vector<int> tree;
    int n;
    
    void updateTree(int index, int val) {
        while (index <= n) {
            tree[index] += val;
            index += index & (-index);
        }
    }
    
    int getSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & (-index);
        }
        return sum;
    }
    
public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
        this->n = nums.size();
        this->tree.resize(n + 1);
        for (int i = 0; i < n; i++) {
            updateTree(i + 1, nums[i]);
        }
    }
    
    void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] = val;
        updateTree(index + 1, diff);
    }
    
    int sumRange(int left, int right) {
        return getSum(right + 1) - getSum(left);
    }
};

执行结果

方法一（C#实现）

• 执行用时：256 ms, 击败45.31%的用户
• 内存消耗：42.1 MB, 击败91.23%的用户

方法二（Python实现）

• 执行用时：128 ms, 击败85.64%的用户
• 内存消耗：17.8 MB, 击败75.32%的用户

方法三（C++实现）

• 执行用时：68 ms, 击败99.12%的用户
• 内存消耗：16.8 MB, 击败94.23%的用户

代码亮点

1. 🎯 提供多种实现方案，适应不同场景需求
2. 💡 分块处理方法巧妙平衡更新和查询的性能
3. 🔍 树状数组实现高效的区间和查询
4. 🎨 代码结构清晰，易于理解和维护

常见错误分析

1. 🚫 使用累加数组，无法高效处理更新操作
2. 🚫 分块大小选择不当，影响整体性能
3. 🚫 树状数组索引计算错误
4. 🚫 未考虑边界情况的处理

相关题目

• LeetCode 303. 区域和检索 - 数组不可变 - 简单
• LeetCode 304. 二维区域和检索 - 矩阵不可变 - 中等
• LeetCode 308. 二维区域和检索 - 可变 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第307题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！