LeetCode 问题练习和总结：区域和检索 - 可修改数组 - 307 - 输入： ["NumArray", "sumRange", "update", "sumRange"］ [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] 输出： [空，9，空，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 + 3 + 5 = 9 numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8 小贴士

最编程 2024-10-15 09:21:43

...

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

二、解题思路

这个问题可以通过使用一个数据结构来优化区间和查询的效率，这个数据结构通常被称为树状数组（Binary Indexed Tree, BIT）或者线段树（Segment Tree）。由于树状数组在实现上较为简洁，我们这里采用树状数组来解决问题。

解题思路：

使用一个额外的数组 tree 来构建树状数组，其中 tree[i] 用于存储从 nums[i - 2^r + 1] 到 nums[i] 的元素和，这里 r 是 i 二进制表示中最低位的 1 所在的位置。
在 NumArray 构造函数中初始化树状数组。
在 update 方法中，首先计算出需要更新的元素的新值与旧值的差值，然后更新 nums 数组中对应位置的值，接着更新树状数组。
在 sumRange 方法中，计算从 left 到 right 的区间和。

三、具体代码

class NumArray {
    private int[] nums;
    private int[] tree;
    private int n;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.tree = new int[n + 1];
        for (int i = 0; i < n; 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);
    }

    private void add(int index, int val) {
        while (index <= n) {
            tree[index] += val;
            index += index & -index;
        }
    }

    private int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

上一篇：使用 MailKit 在 C# 中收发电子邮件

下一篇：面试问题 - 请告诉我们 rpc 和 http 的区别，以及 http 能否取代 kafka。