最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(8.6)线段树中的更新操作

    307. 区域和检索 – 数组可修改

    给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

    update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。

    说明:

    1. 数组仅可以在 update 函数下进行修改。
    2. 你可以认为调用 update 函数和 sumRange 函数的次数是相等的。

    这个问题我们先使用预处理数组的方式解决

    class NumArray {
    
        private int[] data;
        private int[] sum;
        public NumArray3(int[] nums) {
    
            data = new int[nums.length];
            for(int i = 0 ; i < nums.length ; i ++)
                data[i] = nums[i];
    
            sum = new int[nums.length + 1];
            sum[0] = 0;
            for(int i = 1 ; i <= nums.length ; i ++)
                sum[i] = sum[i - 1] + nums[i - 1];
        }
    
        public int sumRange(int i, int j) {
            return sum[j + 1] - sum[i];
        }
    
        public void update(int index, int val) {
            data[index] = val;
            for(int i = index + 1 ; i < sum.length ; i ++)
                sum[i] = sum[i - 1] + data[i - 1];
        }
    }
    

    提交LeetCode发现超时……

    线段树中的更新操作

    为了解决上述LeetCode中307号问题,我们为线段树增加更新操作

    // 将index位置的值,更新为e
    public void set(int index, E e){
    
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal");
    
        data[index] = e;
        set(0, 0, data.length - 1, index, e);
    }
    
    // 在以treeIndex为根的线段树中更新index的值为e
    private void set(int treeIndex, int l, int r, int index, E e){
    
        if(l == r){
            tree[treeIndex] = e;
            return;
        }
    
        int mid = l + (r - l) / 2;
        // treeIndex的节点分为[l...mid]和[mid+1...r]两部分
    
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if(index >= mid + 1)
            set(rightTreeIndex, mid + 1, r, index, e);
        else // index <= mid
            set(leftTreeIndex, l, mid, index, e);
    
        tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }
    

    继续解决307号问题

    class NumArray {
    
        private SegmentTree segTree;
        public NumArray(int[] nums) {
    
            if(nums.length != 0){
                Integer[] data = new Integer[nums.length];
                for(int i = 0 ; i < nums.length ; i ++)
                    data[i] = nums[i];
                segTree = new SegmentTree<>(data, (a, b) -> a + b);
            }
        }
    
        public void update(int i, int val) {
            if(segTree == null)
                throw new IllegalArgumentException("Error");
            segTree.set(i, val);
        }
    
        public int sumRange(int i, int j) {
            if(segTree == null)
                throw new IllegalArgumentException("Error");
            return segTree.query(i, j);
        }
    }
    

    成功通过!

    源码下载

    [dm href='https://www.geekerstar.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.geekerstar.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(8.6)线段树中的更新操作

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 211会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 869稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级