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

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

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

给定一个整数数组 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.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

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

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(8.6)线段树中的更新操作
分享到:
赞(0)

评论抢沙发

评论前必须登录!