0307. 区域和检索 - 数组可修改【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 树状数组

1. 📝 题目描述

• leetcode

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

1. 其中一类查询要求 更新 数组 nums 下标对应的值
2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的 nums 元素的 和，其中 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 元素的 和 （即，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
• 调用 update 和 sumRange 方法次数不大于 3 * 10^4

2. 🎯 s.1 - 树状数组

c

typedef struct {
    int* tree;
    int* nums;
    int n;
} NumArray;

NumArray* numArrayCreate(int* nums, int numsSize) {
    NumArray* obj = (NumArray*)malloc(sizeof(NumArray));
    obj->n = numsSize;
    obj->tree = (int*)calloc(numsSize + 1, sizeof(int));
    obj->nums = (int*)calloc(numsSize, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        int delta = nums[i];
        obj->nums[i] = nums[i];
        for (int j = i + 1; j <= numsSize; j += j & (-j))
            obj->tree[j] += delta;
    }
    return obj;
}

void numArrayUpdate(NumArray* obj, int index, int val) {
    int delta = val - obj->nums[index];
    obj->nums[index] = val;
    for (int i = index + 1; i <= obj->n; i += i & (-i))
        obj->tree[i] += delta;
}

int query(NumArray* obj, int i) {
    int s = 0;
    for (; i > 0; i -= i & (-i)) s += obj->tree[i];
    return s;
}

int numArraySumRange(NumArray* obj, int left, int right) {
    return query(obj, right + 1) - query(obj, left);
}

void numArrayFree(NumArray* obj) {
    free(obj->tree); free(obj->nums); free(obj);
}

js

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

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function (index, val) {
  const delta = val - this.nums[index]
  this.nums[index] = val
  for (let i = index + 1; i <= this.n; i += i & -i) {
    this.tree[i] += delta
  }
}

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
  const query = (i) => {
    let s = 0
    for (; i > 0; i -= i & -i) s += this.tree[i]
    return s
  }
  return query(right + 1) - query(left)
}

py

class NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = [0] * self.n
        self.tree = [0] * (self.n + 1)
        for i, v in enumerate(nums):
            self.update(i, v)

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def sumRange(self, left: int, right: int) -> int:
        def query(i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & (-i)
            return s
        return query(right + 1) - query(left)

• 时间复杂度：初始化 $O(n\log n)$，update 和 sumRange 均为 $O(\log n)$
• 空间复杂度：$O(n)$

算法思路：

• 使用树状数组（Binary Indexed Tree）维护前缀和
• update 时从当前索引向上更新所有包含该元素的节点
• sumRange 通过两次前缀和查询相减得到区间和