LeetCode刷题实战307：区域和检索 - 数组可修改

程序员小猿

发布于 2021-07-06 16:14:38

5000

文章被收录于专栏：程序IT圈程序IT圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 区域和检索 - 数组可修改，我们先来看题面：

https://leetcode-cn.com/problems/range-sum-query-mutable/

给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。

示例

输入：
["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); // 返回 9 ，sum([1,3,5]) = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 8

解题

https://blog.csdn.net/qq_36452584/article/details/107166128

线段树（Segment Tree）

我们可以构造一种特殊的数据结构——线段树，线段树常用来处理数组相应的区间查询（range query）和元素更新（update）操作。线段树算是一种比较高级的树结构，这里作为了解即可。

这题使用的是树状数组。树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多。

int[] tree;
int n;
public NumArray(int[] nums) {
    if (nums.length > 0) {
        n = nums.length;
        tree = new int[n * 2];
        buildTree(nums);
    }
}
private void buildTree(int[] nums) {
    for (int i = n, j = 0; i < 2 * n; i++, j++)
        tree[i] = nums[j];
    for (int i = n - 1; i > 0; --i)
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-06-28，如有侵权请联系 cloudcommunity@tencent.com 删除

https

网络安全

编程算法

本文分享自程序员小猿微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

https

网络安全

编程算法

登录后参与评论

0 条评论

热度