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

简介: 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])

示例 1:

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

解题

方法一:线段树

struct Node{
    Node* left;
    Node* right;
    int val;
    int add;
};
class NumArray {
public:
    Node* root=new Node();
    int N;
    NumArray(vector<int>& nums) {
        N=nums.size()-1;
        for(int i=0;i<=N;i++){
            update(root,0,N,i,i,nums[i]);
        }
    }
    void update(int index, int val) {
        update(root,0,N,index,index,val);
    }
    int sumRange(int left, int right) {
        return query(root,0,N,left,right);
    }
private:
    void update(Node* node,int start,int end,int l,int r,int val){
        if(l<=start&&end<=r){
            node->val=(end-start+1)*val;
            node->add=val;
            return;
        }
        int mid=(start+end)>>1;
        pushDown(node,mid-start+1,end-mid);
        if(l<=mid) update(node->left,start,mid,l,r,val);
        if(r>mid) update(node->right,mid+1,end,l,r,val);
        pushUp(node);
    }
    int query(Node* node,int start,int end,int l,int r){
        if(l<=start&&end<=r) return node->val;
        int mid=(start+end)>>1;
        int res=0;
        pushDown(node,mid-start+1,end-mid);
        if(l<=mid) res+=query(node->left,start,mid,l,r);
        if(r>mid) res+=query(node->right,mid+1,end,l,r);
        return res;
    }
    void pushUp(Node* node){
        node->val=node->left->val+node->right->val;
    }
    void pushDown(Node* node,int leftNum,int rightNum){
        if(node->left==nullptr) node->left=new Node();
        if(node->right==nullptr) node->right=new Node();
        if(node->add==0) return;
        node->left->val=node->add*leftNum;
        node->right->val=node->add*rightNum;
        node->left->add=node->add;
        node->right->add=node->add;
        node->add=0;
    }
};
相关文章
|
27天前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
22天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
17 4
|
22天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
14 0
Leetcode第三十三题(搜索旋转排序数组)
|
22天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
47 0
|
22天前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
13 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组