• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(8.6)线段树中的更新操作

极客笔记 Geekerstar 11个月前 (05-20) 410次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

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<Integer> 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);
    }
}

成功通过!

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(8.6)线段树中的更新操作
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00