Leetcode-307-区域和检索-数组可修改

题目

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

  1. 其中一类查询要求 更新 数组 nums 下标对应的值

  2. 另一类查询要求返回数组 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]）

解题思路

暴力法

根据题意不难直接写出暴力解决方案, 当然直接TLE

可以得出, 更新操作时间复杂度O(1)O(1), 求和操作时间复杂度O(r−l)O(r-l)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray {
public:
    vector<int>& nums;
    NumArray(vector<int>& nums): nums(nums) {}

    void update(int index, int val) {
        nums[index] = val;
    }

    int sumRange(int left, int right) {
        int s = 0;
        for(int i=left;i<=right;i++) s+=nums[i];
        return s;
    }
};

线段树

线段树讲解

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在O(log(N))O(log(N))的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

如下图, 有数组[10, 11, 12, 13, 14] 我们可以把区间[1, 5]划分为2份, 4份, 5份, 直到划分为单点

对区间[start, end]的划分算法如下,

计算区间中点mid = (start + end) / 2

  • 划分得到左区间[start, mid]

  • 划分得到右区间[mid+1, end]

最后可得到如下的一棵树,

数据结构定义

由此, 可轻易写出如下结构体定义, 表示线段树上的某个区间结点

1
2
3
4
5
6
7
8
9
10
11
12
struct TreeNode {
    int start;
    int end;
    int sum;
    TreeNode *left;
    TreeNode *right;

    void display(int deep) {
        for (int i = 0; i < deep; i++) cout << "    ";
        cout << "[" << start << ", " << end << "] (" << sum << ")" << endl;
    }
};

建立线段树

建立线段树即给定一个数组, 建立一棵线段树

算法流程

  1. 开辟树根结点

  2. 计算中点mid

  3. 判断区间左右端点大小

    1. start < end: 即区间还可以继续划分

      1. 对区间[start, mid]建立线段树作为根结点的左子树

      2. 对区间[mid+1, end]建立线段树作为根结点的右子树

      3. 更新树根结点的sum值为两子树sum之和

    2. start == end: 区间已为单点区间, 不可继续划分

      1. 置左右子树为空

      2. 更新树根结点的sum值为单点元素值

  4. 返回树根结点即为所建立的线段树

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode *buildTree(vector<int> nums, int start, int end) {
    int mid = (end - start) / 2 + start;
    TreeNode *root = new TreeNode;
    root->start = start;
    root->end = end;
    if (start < end) {
        root->left = buildTree(nums, start, mid);
        root->right = buildTree(nums, mid + 1, end);
        root->sum = root->left->sum + root->right->sum;
    } else if (start == end) {
        root->left = root->right = nullptr;
        root->sum = nums[start];
    }

    return root;
}

单点更新

线段树的单点更新即更新指定下标处的值, 修改这棵线段树

算法流程

已知update函数可以修改某个线段树中指定下标的值

  1. 判断是否为叶子结点, 如果是叶子结点

    1. 直接更新sum值

  2. 如果不是叶子结点

    1. 更新子线段树

      1. 若下标在左子树, 则调用update函数更新左子线段树

      2. 若下标在右子树, 则调用update函数更新右子线段树

    2. 最后更新区间和, 该结点的sum值为两子线段树的sum值之和

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void update(TreeNode *node, int index, int val) {
    // 找到叶子
    if (node->start == node->end) {
        node->sum = val;
        return;
    } else {
        int mid = (node->end - node->start) / 2 + node->start;
        if (index <= mid) {
            // 要更新的东西在左子树
            update(node->left, index, val);
        } else {
            // 要更新的东西在右子树
            update(node->right, index, val);
        }
        // 更新区间和
        node->sum = node->left->sum + node->right->sum;
    }
}

区间求和

线段树的区间求和即给定一个区间[left, right], 求该区间的所有值之和

算法流程

已知query函数可以求处区间[left, right]的所有值之和

  1. 若所求区间正好为单点, 即叶子结点, 那么就直接返回该结点的sum值

  2. 计算线段树根结点的中点mid值

  3. 若所求区间整体在树根的左子线段树区间(right <= mid), 那么直接在左子线段树中求query操作的值为返回结果

  4. 若所求区间整体在树根的右子线段树区间(left>mid), 那么直接在右子线段树中求query操作的值为返回结果

  5. 最后一种情况就是所求区间一部分在左边, 一部分在右边, 需要分割求解

    1. 在树根的左子线段树中计算[left, mid]的query

    2. 在树根的右子线段树中计算[mid+1, right]的query

    3. 左右区间的query结果求和作为返回结果

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    int query(TreeNode *node, int left, int right) {
    // 如果正好就是所求区间
    if (node->start == left && node->end == right) return node->sum;
    int mid = (node->end - node->start) / 2 + node->start;

    // 右边界都在左边,那就往左找
    if (right <= mid) return query(node->left, left, right);

    // 左边界都在右边,向右找
    if (left > mid) return query(node->right, left, right);

    // 一部分在左边,一部分在右边,需要分割
    return query(node->left, left, mid) +
           query(node->right, mid + 1, right);
}

整体代码

C++实现

注意, 这里的线段树代码仍然会TLE

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
class NumArray {
    struct TreeNode {
        int start;
        int end;
        int sum;
        TreeNode *left;
        TreeNode *right;

        void display(int deep) {
            for (int i = 0; i < deep; i++) cout << "    ";
            cout << "[" << start << ", " << end << "] (" << sum << ")" << endl;
        }
    };

public:
    TreeNode *root;
    NumArray(vector<int>& nums) {
        root = buildTree(nums, 0, nums.size()-1);
    }

    void update(int index, int val) {
        update(root, index, val);
    }

    int sumRange(int left, int right) {
        return query(root, left, right);
    }

    TreeNode *buildTree(vector<int> nums, int start, int end) {
        int mid = (end - start) / 2 + start;
        TreeNode *root = new TreeNode;
        root->start = start;
        root->end = end;
        if (start < end) {
            root->left = buildTree(nums, start, mid);
            root->right = buildTree(nums, mid + 1, end);
            root->sum = root->left->sum + root->right->sum;
        } else if (start == end) {
            root->left = root->right = nullptr;
            root->sum = nums[start];
        }

        return root;
    }

    void update(TreeNode *node, int index, int val) {
        // 找到叶子
        if (node->start == node->end) {
            node->sum = val;
            return;
        } else {
            int mid = (node->end - node->start) / 2 + node->start;
            if (index <= mid) {
                // 要更新的东西在左子树
                update(node->left, index, val);
            } else {
                // 要更新的东西在右子树
                update(node->right, index, val);
            }
            // 更新区间和
            node->sum = node->left->sum + node->right->sum;
        }
    }

    int query(TreeNode *node, int left, int right) {
        // 如果正好就是所求区间
        if (node->start == left && node->end == right) return node->sum;
        int mid = (node->end - node->start) / 2 + node->start;

        // 右边界都在左边,那就往左找
        if (right <= mid) return query(node->left, left, right);

        // 左边界都在右边,向右找
        if (left > mid) return query(node->right, left, right);

        // 一部分在左边,一部分在右边,需要分割
        return query(node->left, left, mid) +
               query(node->right, mid + 1, right);
    }
};

Java实现

但是同样的算法如果我们换成java实现却能AC, 很迷

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
class NumArray {
    class TreeNode {
        int start, end, sum;
        TreeNode left, right;
    }

    TreeNode buildTree(int[] nums, int start, int end) {
        int mid = (end - start) / 2 + start;
        TreeNode root = new TreeNode();
        root.start = start;
        root.end = end;
        if (start < end) {
            root.left = buildTree(nums, start, mid);
            root.right = buildTree(nums, mid + 1, end);
            root.sum = root.left.sum + root.right.sum;
        } else if (start == end) {
            root.left = null;
            root.right = null;
            root.sum = nums[start];
        }

        return root;
    }

    // 查询区间和
    int query(TreeNode node, int left, int right) {
        // 如果正好就是所求区间
        if (node.start == left && node.end == right)
            return node.sum;
        int mid = (node.end - node.start) / 2 + node.start;

        // 右边界都在左边,那就往左找
        if (right <= mid)
            return query(node.left, left, right);

        // 左边界都在右边,向右找
        if (left > mid)
            return query(node.right, left, right);

        // 一部分在左边,一部分在右边,需要分割
        return query(node.left, left, mid) +
                query(node.right, mid + 1, right);
    }

    // 更新线段树
    void update(TreeNode node, int index, int val) {
        // 找到叶子
        if (node.start == node.end) {
            node.sum = val;
            return;
        } else {
            int mid = (node.end - node.start) / 2 + node.start;
            if (index <= mid) {
                // 要更新的东西在左子树
                update(node.left, index, val);
            } else {
                // 要更新的东西在右子树
                update(node.right, index, val);
            }
            // 更新区间和
            node.sum = node.left.sum + node.right.sum;
        }
    }

    TreeNode root;

    public NumArray(int[] nums) {
        root = buildTree(nums, 0, nums.length - 1);
    }

    public void update(int index, int val) {
        update(root, index, val);
    }

    public int sumRange(int left, int right) {
        return query(root, left, right);
    }
}

分析总结

估计大概率是存储结构的问题(可能new性能不高), 由于考虑到线段树是一颗完全二叉树, 故可考虑优化成堆存储(即通过数组存储), 减少通过new开辟内存的次数, 完全可以一次性开辟足够存放的数组.