What is the time complexity for range sum queries and updates?

Using a Binary Indexed Tree or Segment Tree, both operations can be handled in O(log n) time. The brute force approach has O(n) time complexity per query.

Can the solution handle large input sizes efficiently?

Yes, using advanced data structures like BIT or Segment Tree can efficiently handle arrays with sizes up to 30,000 and handle up to 30,000 operations.

What is the main challenge in this problem?

The main challenge is to efficiently handle both update and range sum queries on a mutable array, which requires careful selection of data structures.

Is the problem solvable using a simple array?

While an array can store the data, a simple array would be inefficient for range sum queries and updates, leading to slow performance for large inputs.

How does a Binary Indexed Tree work for this problem?

A Binary Indexed Tree stores cumulative sums at various levels, allowing efficient updates and range queries by maintaining partial sums and reducing the need for full array scans.

#307

Medium

auto_awesome数组·结合·design

LeetCode 题解工作台

区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。其中一类查询要求更新数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和，其中 left 实现 NumArray 类： NumArray(int[] nums) …

数组设计树状数组线段树

题目描述

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

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 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⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 10⁴

lightbulb

解题思路

方法一：树状数组

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。它可以高效地实现如下两个操作：

单点更新 $update(x, delta)$ ：把序列 $x$ 位置的数加上一个值 $delta$ ；
前缀和查询 $query(x)$ ：查询序列 $[1,...x]$ 区间的区间和，即位置 $x$ 的前缀和。

这两个操作的时间复杂度均为 $O(\log n)$ 。

树状数组最基本的功能就是求比某点 $x$ 小的点的个数（这里的比较是抽象的概念，可以是数的大小、坐标的大小、质量的大小等等）。

对于本题，我们在构造函数中，先创建一个树状数组，然后遍历数组中每个元素的下标 $i$ （从 $1$ 开始）和对应的值 $v$ ，调用 $update(i, v)$ ，即可完成树状数组的初始化。时间复杂度为 $O(n \log n)$ 。

对于 $sumRange(left, right)$ ，我们可以通过 $query(right + 1) - query(left)$ 得到区间和。时间复杂度为 $O(\log n)$ 。

对于 $update(index, val)$ ，我们可以先通过 $sumRange(index, index)$ 得到原来的值 $prev$ ，然后调用 $update(index, val - prev)$ ，即可完成更新。时间复杂度为 $O(\log n)$ 。

空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int):
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s


class NumArray:
    __slots__ = ["tree"]

    def __init__(self, nums: List[int]):
        self.tree = BinaryIndexedTree(len(nums))
        for i, v in enumerate(nums, 1):
            self.tree.update(i, v)

    def update(self, index: int, val: int) -> None:
        prev = self.sumRange(index, index)
        self.tree.update(index + 1, val - prev)

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


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate suggest a more efficient solution than brute force?
question_mark
Does the candidate understand the trade-offs between different data structures like BIT and Segment Tree?
question_mark
How well does the candidate describe optimizing time complexity for both sum queries and updates?

warning

常见陷阱

外企场景

error
Not recognizing that a brute force solution may be too slow for large inputs.
error
Failing to implement efficient update handling in the chosen data structure.
error
Incorrectly managing the data structure’s memory usage, especially with Segment Trees.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing with a Binary Indexed Tree instead of a Segment Tree.
arrow_right_alt
Supporting additional operations like range minimum query alongside sum queries.
arrow_right_alt
Optimizing space complexity by adjusting the data structure size or approach.

help

常见问题

外企场景

继续练习

#1157 子数组中占绝大多数的元素 #315 计算右侧小于当前元素的个数 #327 区间和的个数