307. Range Sum Query - Mutable | 307. 区域和检索 - 数组可修改（数据结构：线段树，图文详解）

川长思鸟来 2022-10-13 05:26 134阅读 0赞

## 题目 ##

[https://leetcode.com/problems/range-sum-query-mutable/][https_leetcode.com_problems_range-sum-query-mutable]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

--------------------

## 吐槽官方题解 ##

这题的 [英文版官方题解][Link 1]，配图和代码不一致，而且描述不清；力扣国内版题解完全照搬英文的，机翻让人看不懂。

而且，答案里有一个我没有想明白的细节，就是当数组为奇数的时候，按照它的解法构造的树，就不是一个线段树了，而且 tree 数组节点个数为 `n*2`，它作为一棵满二叉树，节点个数本应为 `n*2-1`，空出第 0 个元素本来不应该有含义，但题解的代码却可以计算出一个确定的值，没有理解表示的是什么，而且这个值的正确与否会影响最终结果的正确性。

评论有人说，数组为奇数的情况下，构造出的是一组完全二叉树，但我还是没有懂。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
**总的来说，题解的代码没有问题（在一些我不懂的地方很巧妙），但细节比较 trick，无法理解是怎么运作的。**

（当然也可能是因为我太菜，如果有明白的大佬，求多多指教~~）

--------------------

## 线段树详解 ##

官方题解看不懂，就另辟蹊径了。参考了灯神的视频：[【数据结构】线段树（Segment Tree）][Segment Tree]，然后关了视频自己实现了一遍，代码和他的过程有一些不同的地方（一方面是不完全记得视频的思路了，一方面是自己的想法对我来说更好懂一点），不过最后总算 AC 了。

#### 1、构造线段树 construct ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
用空值填充剩余节点，使之成为完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

#### 2、修改树中的元素 update ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

#### 3、范围求和 sumRange ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]  
直接 return 0 的情况：需要计算的范围在当前查询的左右边界之外  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]

#### 4、代码 ####

public class NumArray { 
        int[] nums;
        int[] tree;
    
        public NumArray(int[] nums) { 
            this.nums = nums;
            tree = new int[2 * 2 * 3 * 10000]; // tree数组长度的确定：变成完全二叉树是2倍，考虑最后一层可能有空余填充所以再乘个2倍
            construct(tree, nums, 0, 0, nums.length - 1);
        }
    
        public void construct(int[] tree, int[] nums, int index, int left, int right) { 
            if (left == right) { 
                tree[index] = nums[left];
            } else { 
                int mid = (left + right) / 2;
                construct(tree, nums, 2 * index + 1, left, mid);
                construct(tree, nums, 2 * index + 2, mid + 1, right);
                tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
            }
        }
    
        public void update(int index, int val) { 
            // 找到原数组在线段树中对应的位置
            int left = 0;
            int right = nums.length - 1;
            int treeIndex = 0;
            while (left != right) { 
                int mid = (left + right) / 2;
                if (index <= mid) {  // 走左子树
                    right = mid;
                    treeIndex = treeIndex * 2 + 1;
                } else {  // 走右子树
                    left = mid + 1;
                    treeIndex = treeIndex * 2 + 2;
                }
            }
            // 从下向上更新，类似于堆调整，只不过计算的是“差值”，这是与视频思路不一样的地方
            int dif = val - nums[index];
            while (treeIndex > 0) { 
                tree[treeIndex] += dif;
                treeIndex = (treeIndex - 1) / 2;
            }
            tree[0] += dif;
            nums[index] = val; // 题目中一系列操作是累计的，所以别忘了改原数组。。
        }
    
        public int sumRange(int left, int right) { 
            return sum(tree, 0, 0, nums.length - 1, left, right);
        }
        // 在线段树从begin到end的范围内，找left到right的累加和
        public int sum(int[] tree, int index, int begin, int end, int left, int right) { 
            if (begin > right || end < left) return 0;
            if (begin == end || begin >= left && end <= right) return tree[index];
            int mid = (begin + end) / 2;
            return sum(tree, 2 * index + 1, begin, mid, left, right) +
                    sum(tree, 2 * index + 2, mid + 1, end, left, right);
        }
    }
    
    /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.update(index,val); * int param_2 = obj.sumRange(left,right); */

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

[https_leetcode.com_problems_range-sum-query-mutable]: https://leetcode.com/problems/range-sum-query-mutable/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/914607c986334d84839b41c88b453c3c.png
[Link 1]: https://leetcode.com/problems/range-sum-query-mutable/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/3aa1563f10544e8c8cfd1d1dc2b4f04f.png
[Segment Tree]: https://www.bilibili.com/video/av47331849/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/d52b0a01853542d3986800cf2b5d925b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/08dcc8c31df24dcabd7edc6315838ee5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/cf793f31c0c8425d8f0cf8a1f83dac29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 2]: /images/20221005/3f693c92de5b460ebea1dfad55e31a18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 3]: /images/20221005/5814e78ddfda4c18be23d81f351f8b6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20221005/65cbe4d1b1ed4d9c8bb0f7e4d7be40bc.png