数据结构 玩转数据结构 9-6 线段树中的更新操作

标签：index return int tree mid length 玩转 数据结构 树中

0　　　　课程地址

https://coding.imooc.com/lesson/207.html#mid=13848

 

1　　　　重点关注

1.1　　　　线段树中的更新操作

见3.1

 

 

2　　　　课程内容

 

 

3　　　　Coding

3.1　　　　leetCode307问题解析

• 需求

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

    其中一类查询要求 更新 数组 nums 下标对应的值
    另一类查询要求返回数组 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

 

提示：

    1 <= nums.length <= 3 * 104
    -100 <= nums[i] <= 100
    0 <= index < nums.length
    -100 <= val <= 100
    0 <= left <= right < nums.length
    调用 update 和 sumRange 方法次数不大于 3 * 104 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/range-sum-query-mutable

 

• 代码实现

package com.company;

/**
 * 线段树
 * 根据入参数组的元素个数，制造出线段树节点元素个数
 * @author weidoudou
 * @date 2023/1/15 15:24
 **/
public class SegmentTree<E> {
    //1     初始化线段树元素和数组元素
    private E[] data;
    private E[] tree;
    private Merge<E> merger;

    /**
     * 初始化数组元素和tree(4*元素个数上节有推导)
     * @author weidoudou
     * @date 2023/1/15 15:34
     * @param nums 请添加参数描述
     * @return null
     **/
    public SegmentTree(E [] nums,Merge<E> merger){
        data = (E[])new Object[nums.length];
        for(int i = 0; i < nums.length; i++){
            data[i] = nums[i];
        }

        this.merger = merger;

        tree = (E[])new Object[4*nums.length];
        buildSegmentTree(0,0,data.length-1);
    }

    //2     创建线段树
    private void buildSegmentTree(int index,int l,int r){
        //2.1   终止条件
        if(l==r){
            tree[index] = data[l];

        //2.2   循环条件
        }else{
            //定义mid 将线段树节点平均拆分
            int mid = l+(r-l)/2;
            int indexL = getLeftChild(index);
            int indexR = getRightChild(index);
            buildSegmentTree(indexL,l,mid);
            buildSegmentTree(indexR,mid+1,r);
            tree[index] = merger.merge(tree[indexL],tree[indexR]);
        }

    }

    //3     查询线段树区间
    public E query(int queryL,int queryR){
        if(queryL<0||queryR>= data.length||queryL>queryR){
            throw new IllegalArgumentException("index is error");
        }
        return query(queryL,queryR,0,0, data.length-1);
    }

    private E query(int queryL,int queryR,int index,int l,int r){

        if(queryL == l&&queryR == r){
            return tree[index];
        }

        int mid = l+(r-l)/2;
        int leftIndex = getLeftChild(index);
        int rightIndex = getRightChild(index);

        //如果
        if(queryL>=mid+1){
            return query(queryL,queryR,rightIndex,mid+1,r);
        }else if(queryR<=mid){
            return query(queryL, queryR,leftIndex,l,mid);
        }else{
            E leftE = query(queryL, mid,leftIndex,l,mid);
            E rightE = query(mid+1,queryR,rightIndex,mid+1,r);
            return merger.merge(leftE, rightE);
        }
    }

    //5     更新线段树
    public void set(int index,E e){
        if(index<0||index>data.length-1){
            throw new IllegalArgumentException("索引不正确");
        }
        data[index] = e;

        //递归调用，更新
        set(0,0,data.length-1,index,e);
    }

    /**
     * 递归调用更新线段树的值，注意：我理解，这个更新的节点一定是在叶子节点吧
     * @author weidoudou
     * @date 2023/1/21 7:02
     * @param root 每次递归相应的父节点
     * @param  l 每次递归相应的左节点
     * @param  r 每次递归相应的右节点
     * @param  index 更新的树中的索引
     * @param  e 更新成的元素
     * @return void
     **/
    private void set(int root,int l,int r,int index,E e){
        //2.1   终止条件
        if(l==r){
            tree[root] = e;
            return;

            //2.2   循环条件
        }else{
            //定义mid 将线段树节点平均拆分
            int mid = l+(r-l)/2;
            int indexL = getLeftChild(root);
            int indexR = getRightChild(root);
            if(index>=mid+1){
                set(indexR,mid+1,r,index,e);
            }else{
                set(indexL,l,mid,index,e);
            }
            tree[root] = merger.merge(tree[indexL],tree[indexR]);
        }
    }



    //4     基本方法
    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index<0||index>=getSize()){
            throw new IllegalArgumentException("get失败");
        }
        return data[index];
    }

    public int getLeftChild(int index){
        return index*2+1;
    }

    public int getRightChild(int index){
        return index*2+2;
    }

    public String toString(){
        StringBuffer sbf = new StringBuffer();
        sbf.append("[");
        for(int i = 0;i< tree.length;i++){
            if(tree[i]!=null){
                sbf.append(tree[i]);
            }else{
                sbf.append("null");
            }
            if(i!=tree.length-1){
                sbf.append(",");
            }
        }


        sbf.append("]");
        return sbf.toString();
    }


}

 

• 融合函数

package com.company;

/**
 * 融合函数
 * @author weidoudou
 * @date 2023/1/17 6:38
 **/
public interface Merge<E> {
    E merge(E left,E right);
}

 

• 测试结果

 

 

 

 

标签：index,return,int,tree,mid,length,玩转,数据结构,树中
From： https://www.cnblogs.com/1446358788-qq/p/17066350.html