力扣 307. 区域和检索 - 数组可修改

题目来源：https://leetcode.cn/problems/range-sum-query-mutable/

大致题意：

设计一个类，其包含一个数组，并且有两个方法：

• update(int index, int val)) 将给定索引处的数组元素更新为 val
• sumRange(int left, int right) 返回给定索引范围内的数组元素和

---

思路

直接使用数组实现该类，那么：

• 更新的时间复杂度为 O(1)
• 范围查询的时间复杂度为 O(n)

如果使用前缀和实现该类，那么：

• 更新的时间复杂度为 O(n)
• 范围查询的时间复杂度为 O(1)

而如果使用线段树（适宜进行区间内求和（最值），更新区间和（最值）），那么：

• 更新的时间复杂度为 O(log n)
• 范围查询的时间复杂度为 O(log n)

这道题基本上是线段树模板题，线段树主要包含的操作：

• 建树，自底向上建树
• 更新树，自底向上更新
• 范围查询

具体看代码：

public class NumArray {
    int[] segmentTree;  // 线段树
    int[] nums; // 线段树叶子节点对应的数组
    int n;  // 叶子节点个数

    // 构造器
    // 使用给定数组建树
    public NumArray(int[] nums) {
        // 叶子节点数目即为给定数组长度
        n = nums.length;
        // 线段树初始化
        segmentTree = new int[4 * n];
        this.nums = nums;
        // 递归建树
        build(0, 0, n - 1);
    }

    /**
     * 建树
     * @param node 当前节点编号
     * @param start 当前节点表示的区间左边界
     * @param end 当前节点表示的区间左边界
     */
    public void build(int node, int start, int end) {
        // start 等于 end，表示当前节点是叶子节点，赋值并返回
        if (start == end) {
            segmentTree[node] = nums[start];
            return;
        }
        // 区间中值
        int mid = (start + end) >> 1;
        // 递归构建左子树
        build(node * 2 + 1, start, mid);
        // 递归构建右子树
        build(node * 2 + 2, mid + 1, end);
        // 构建当前节点，本题求的是区间和，所以求和
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    // 更新数组指定索引的元素
    public void update(int index, int val) {
        change(index, 0, 0, n - 1, val);
    }


    /**
     * 递归修改树节点
     * @param idx 要修改元素在数组中的索引
     * @param node  当前线段树节点编号
     * @param start 当前线段树节点对应区间的左边界
     * @param end 当前线段树节点对应区间的右边界
     * @param val 要修改的值
     */
    public void change(int idx, int node, int start, int end, int val) {
        // 如果左右边界相等，表示当前节点即为要修改的目标节点，修改并返回
        if (start == end) {
            segmentTree[node] = val;
            return;
        }
        // 区间中值
        int mid = (start + end) >> 1;
        // 如果待修改节点小于等于区间中值，表示待修改节点对应叶子节点在左子树
        if (idx <= mid) {
            change(idx, node * 2 + 1, start, mid, val);
        } else {    // 待修改节点在右子树
            change(idx, node * 2 + 2, mid + 1, end, val);
        }
        // 更新修改后的区间和
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    // 获取 [left, right] 范围内元素和
    public int sumRange(int left, int right) {
        return range(left, right, 0, 0, n - 1);
    }

    /**
     * 获取 [left, right] 范围内元素和
     * @param left  要获取范围和的左边界
     * @param right 要获取范围和的右边界
     * @param node  当前节点对应编号
     * @param start 当前节点对应左边界
     * @param end   当前节点对应右边界
     * @return
     */
    public int range(int left, int right, int node, int start, int end) {
        // 如果当前节点对应区间与所求范围相同，直接返回当前节点对应区间和
        if (left == start && right == end) {
            return segmentTree[node];
        }
        // 区间中值
        int mid = (start + end) >> 1;
        // 如果待获取范围右边界小于等于区间中值，表示所求范围在当前节点左子树
        if (right <= mid) {
            return range(left, right, node * 2 + 1, start, mid);
        } else if (left > mid) {    // // 如果待获取范围左边界大于区间中值，表示所求范围在当前节点右子树
            return range(left, right, node * 2 + 2, mid + 1, end);
        } else {    // 待获取范围横跨左右子树
            return range(left, mid, node * 2 + 1, start, mid) + range(mid + 1, right, node * 2 + 2, mid + 1, end);
        }
    }
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102