Medium

题目描述

给你一个整数数组 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 之间的元素的和（即 nums[left] + nums[left + 1] + ... + nums[right]）。

示例 1：

输入
["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^4
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • 最多调用 3 * 10^4 次 update 和 sumRange 方法

解题思路

这是一道经典的数据结构设计题，需要在可变数组上支持高效的区间求和查询。有三种常见解法：

解法一：朴素解法 直接用数组存储，update O(1)，sumRange O(n)。当查询次数很多时效率低下。

解法二：树状数组（Binary Indexed Tree）【推荐】 树状数组是专门解决此类问题的数据结构。通过巧妙的二进制位运算，实现单点更新和前缀和查询均为 O(log n)。核心思想是将数组拆分成多个区间，每个节点存储特定区间的和。

解法三：线段树（Segment Tree） 线段树通过递归分治思想，将数组分解为树结构，每个节点表示一个区间。虽然功能更强大，但对于此题来说实现复杂度较高。

树状数组实现简洁且效率高，是这类问题的最优解。通过 lowbit 操作（x & -x）找到最低位的 1，实现高效的区间管理。更新时向上传播影响，查询时累加前缀和。

代码实现

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

class NumArray:

    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = nums[:]
        self.tree = [0] * (self.n + 1)
        
        for i in range(self.n):
            self._add(i + 1, nums[i])
    
    def _lowbit(self, x):
        return x & -x
    
    def _add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)
    
    def _query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        self._add(index + 1, delta)

    def sumRange(self, left: int, right: int) -> int:
        return self._query(right + 1) - self._query(left)

public class NumArray {
    private int[] tree;
    private int[] nums;
    private int n;
    
    private int Lowbit(int x) {
        return x & -x;
    }
    
    private void Add(int i, int delta) {
        for (int j = i; j <= n; j += Lowbit(j)) {
            tree[j] += delta;
        }
    }
    
    private int Query(int i) {
        int sum = 0;
        for (int j = i; j > 0; j -= Lowbit(j)) {
            sum += tree[j];
        }
        return sum;
    }

    public NumArray(int[] nums) {
        this.n = nums.Length;
        this.nums = new int[n];
        this.tree = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            this.nums[i] = nums[i];
            Add(i + 1, nums[i]);
        }
    }
    
    public void Update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        Add(index + 1, delta);
    }
    
    public int SumRange(int left, int right) {
        return Query(right + 1) - Query(left);
    }
}

var NumArray = function(nums) {
    this.n = nums.length;
    this.nums = [...nums];
    this.tree = new Array(this.n + 1).fill(0);
    
    for (let i = 0; i < this.n; i++) {
        this.add(i + 1, nums[i]);
    }
};

NumArray.prototype.lowbit = function(x) {
    return x & -x;
};

NumArray.prototype.add = function(i, delta) {
    for (let j = i; j <= this.n; j += this.lowbit(j)) {
        this.tree[j] += delta;
    }
};

NumArray.prototype.query = function(i) {
    let sum = 0;
    for (let j = i; j > 0; j -= this.lowbit(j)) {
        sum += this.tree[j];
    }
    return sum;
};

NumArray.prototype.update = function(index, val) {
    const delta = val - this.nums[index];
    this.nums[index] = val;
    this.add(index + 1, delta);
};

NumArray.prototype.sumRange = function(left, right) {
    return this.query(right + 1) - this.query(left);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(n log n)O(n)
updateO(log n)O(1)
sumRangeO(log n)O(1)

其中 n 为数组长度。树状数组需要额外 O(n) 的空间存储树结构，所有操作的时间复杂度均为对数级别，非常高效。

相关题目