线段树入门

奋斗吧

擅长邻域：未填写

标签：线段树入门 Html/CSS博客 51CTO博客

2023-06-17 18:24:18 173浏览

线段树入门，基于arr数组构建线段树，我们根节点存储的是区间[0-5]的和，再往下面分叉，左边表示[0-2]的和，右边表示[3-5]的和，以此类推，最后

线段树入门

1、线段树的概念
2、线段树的操作

2.1 构建线段树
2.2 单点修改
2.3 区间查询
2.4 完整代码
2.5 代码优化

1、线段树的概念

$线段树入门_线段树$ 。而未优化的空间复杂度为 $线段树入门_线段树_02$ ，实际应用时一般还要开 $线段树入门_算法_03$ 的数组以免越界，因此有时需要离散化让空间压缩。

我们可以基于一维数组来实现线段树，就跟完全二叉树的实现方式类似，假设当前节点为i,

$线段树入门_java_04$

$线段树入门_算法_05$

本文参考B站视频：数据结构】线段树（Segment Tree）

2、线段树的操作

2.1 构建线段树

$线段树入门_线段树_06$

线段树入门_线段树_07

基于arr数组构建线段树，我们根节点存储的是区间[0-5]的和，再往下面分叉，左边表示[0-2]的和，右边表示[3-5]的和，以此类推，最后所有的叶子节点就是数组中的所有数字。最终构建的线段树如下：

线段树入门_算法_08

保存这个线段树：我们使用一个数组保存，先标记上各个节点的下标，根节点下标为0，根节点的左孩子下表为 $线段树入门_线段树_09$ ，右孩子下标为 $线段树入门_算法_10$ ,依次类推。

线段树入门_二叉树_11

每个节点存储的都是其左孩子和右孩子的和。

这里代码使用递归实现比较好理解

/**
     * 构建树
     * @param arr 原始数组
     * @param tree 线段树数组
     * @param node 当前节点下标
     * @param start 当前节点对应区间的左边界
     * @param end	当前节点对应区间的右边界
     */
    public static void buildTree(int[] arr, int[] tree, int node, int start, int end){
        if(start==end){//
            tree[node]=arr[start];
        }else{
            int mid=(start+end)/2;//从mid将区间分为两半
            int leftNode=2*node+1;//计算左孩子
            int rightNode=2*node+2;//计算右孩子
            //构建左子树
            buildTree(arr,tree,leftNode,start,mid);
            //构建右子树
            buildTree(arr,tree,rightNode,mid+1,end);
            //子树构建好之后，更新父节点的值
            tree[node]=tree[leftNode]+tree[rightNode];
        }
    }

2.2 单点修改

我们判断要修改的点是位于线段树的左子树还是右子树，若是左子树，递归左子树，修改对应节点的值，若是右子树那就递归右子树，修改对应节点的值。

$线段树入门_java_12$ ,如下图所示。

线段树入门_二叉树_13

/**
     * 单点修改：想要将arr[index]=val，修改tree对应位置的值
     * @param arr
     * @param tree
     * @param node 当前节点下标
     * @param start 当前节点对应区间的左边界
     * @param end   当前节点对应区间的右边界
     * @param index 需要更新节点的下标(arr中的下标)arr[index]=val
     * @param val 修改后的值
     */
    public static void updateTree(int[] arr,int[] tree,int node,int start,int end,int index,int val){
        if(start==end){
            arr[index]=val;
            tree[node]=val;
        }else{
            int mid=(start+end)/2;
            int leftNode=2*node+1;
            int rightNode=2*node+2;
            if(index>=start&&index<=mid){   //要修改的值在左子树中
                updateTree(arr,tree,leftNode,start,mid,index,val);
            }else{  //要修改的值在右子树中
                updateTree(arr,tree,rightNode,mid+1,end,index,val);
            }
            //更新父节点的值
            tree[node]=tree[leftNode]+tree[rightNode];
        }
    }

2.3 区间查询

$线段树入门_数据结构_14$ 的和，

先查询左子树 $线段树入门_数据结构_15$ ,再查询右子树 $线段树入门_java_16$ ,满足 $线段树入门_java_17$ ，直接返回 $线段树入门_二叉树_18$ 。
查询右子树 $线段树入门_二叉树_19$ ，由于 $线段树入门_二叉树_19$ 存在区间覆盖(节点2就是区间 $线段树入门_数据结构_21$ 的和)，所以满足条件L<=start&&end<=R，直接返回 $线段树入门_算法_22$ （我们在2.2中修改了值）
再将左子树和右子树的结果求和: $线段树入门_java_23$

线段树入门_数据结构_24

//区间查询：查询L-R区间的和
    public static int queryTree(int[] arr,int[] tree,int node,int start,int end,int L,int R){
        if(R<start||L>end){ //要查询的区间不在查询的范围之内
            return 0;
        } else if(L<=start&&end<=R){    //是否区间覆盖，可以直接返回tree[node]
            return tree[node];
        }else if(start==end){   //一直查到了叶子节点
            return tree[node];
        }else{
            int mid=(start+end)/2;
            int leftNode=2*node+1;
            int rightNode=2*node+2;
            //查询左子树
            int sumLeft=queryTree(arr,tree,leftNode,start,mid,L,R);
            //查询右子树
            int sumRight=queryTree(arr,tree,rightNode,mid+1,end,L,R);
            //将左右子树的结果相加即可
            return sumLeft+sumRight;
        }
    }

2.4 完整代码

package study.线段树;

import javax.xml.transform.Source;
import java.util.Arrays;

public class SegTree {
    public static final int MAX_LEN=1000;

    public static void main(String[] args) {
        int[] arr={1,3,5,7,9,11};
        int size=arr.length;
        int[] tree=new int[MAX_LEN];

        buildTree(arr,tree,0,0,size-1);
        System.out.println("构建树：");
        Arrays.stream(tree).limit(15).forEach(x-> System.out.print(x+" "));
        System.out.println("\n-------------------------------------");
        //修改测试
        updateTree(arr,tree,0,0,size-1,4,6);
        System.out.println("单点修改:arr[4]=6:");
        Arrays.stream(tree).limit(15).forEach(x-> System.out.print(x+" "));
        System.out.println("\n-------------------------------------");
        //查询测试
        System.out.println("区间查询：[2-5]");
        int sum = queryTree(arr, tree, 0, 0, size - 1, 2, 5);
        System.out.println(sum);

    }

    /**
     * 构建树
     * @param arr 原始数组
     * @param tree 线段树数组
     * @param node  当前节点下标
     * @param start
     * @param end
     */
    public static void buildTree(int[] arr, int[] tree, int node, int start, int end){
        if(start==end){//
            tree[node]=arr[start];
        }else{
            int mid=(start+end)/2;//从mid将区间分为两半
            int leftNode=2*node+1;//计算左孩子
            int rightNode=2*node+2;//计算右孩子
            //构建左子树
            buildTree(arr,tree,leftNode,start,mid);
            //构建右子树
            buildTree(arr,tree,rightNode,mid+1,end);
            //子树构建好之后，更新父节点的值
            tree[node]=tree[leftNode]+tree[rightNode];
        }
    }
    /**
     * 单点修改：想要将arr[index]=val，修改tree对应位置的值
     * @param arr
     * @param tree
     * @param node 当前节点下标
     * @param start 当前节点对应区间的左边界
     * @param end   当前节点对应区间的右边界
     * @param index 需要更新节点的下标(arr中的下标)arr[index]=val
     * @param val 修改后的值
     */
    public static void updateTree(int[] arr,int[] tree,int node,int start,int end,int index,int val){
        if(start==end){
            arr[index]=val;
            tree[node]=val;
        }else{
            int mid=(start+end)/2;
            int leftNode=2*node+1;
            int rightNode=2*node+2;
            if(index>=start&&index<=mid){   //要修改的值在左子树中
                updateTree(arr,tree,leftNode,start,mid,index,val);
            }else{  //要修改的值在右子树中
                updateTree(arr,tree,rightNode,mid+1,end,index,val);
            }
            //更新父节点的值
            tree[node]=tree[leftNode]+tree[rightNode];
        }
    }
    //区间查询：查询L-R区间的和
    public static int queryTree(int[] arr,int[] tree,int node,int start,int end,int L,int R){
        if(R<start||L>end){ //要查询的区间不在查询的范围之内
            return 0;
        } else if(L<=start&&end<=R){    //是否区间覆盖，可以直接返回tree[node]
            return tree[node];
        }else if(start==end){   //一直查到了叶子节点
            return tree[node];
        }else{
            int mid=(start+end)/2;
            int leftNode=2*node+1;
            int rightNode=2*node+2;
            //查询左子树
            int sumLeft=queryTree(arr,tree,leftNode,start,mid,L,R);
            //查询右子树
            int sumRight=queryTree(arr,tree,rightNode,mid+1,end,L,R);
            //将左右子树的结果相加即可
            return sumLeft+sumRight;
        }
    }
}

线段树入门_算法_25

2.5 代码优化

$线段树入门_java_26$ 大小就可以保证不会出现越界了。

package study.线段树;

import java.util.Arrays;

public class SegTree1 {
    public static int[] arr={1,3,5,7,9,11};
    //线段树数组开到4*n就可以保证不会出现越界访问
    public static int[] tree=new int[4*arr.length];

    public static void main(String[] args) {
        buildTree(0,0,arr.length-1);
        System.out.println("构建树：");
        Arrays.stream(tree).limit(15).forEach(x-> System.out.print(x+" "));
        System.out.println("\n-------------------------------------");
        //修改测试
        updateTree(0,0,arr.length-1,4,6);
        System.out.println("单点修改:arr[4]=6:");
        Arrays.stream(tree).limit(15).forEach(x-> System.out.print(x+" "));
        System.out.println("\n-------------------------------------");
        //查询测试
        System.out.println("区间查询：[2-5]");
        int sum=queryTree(0,0,arr.length-1,2,5);
        System.out.println(sum);
    }

    /**
     * 构建树
     * @param node
     * @param start
     * @param end
     */
     public static void buildTree(int node,int start,int end){
        if(start==end){
            tree[node]=arr[start];
        }else{
            int mid=(start+end)/2;
            int leftNode=2*node+1;
            int rightNode=2*node+2;
            //构建左子树
            buildTree(leftNode,start,mid);
            //构建右子树
            buildTree(rightNode,mid+1,end);
            //子树构建好之后，更新父节点的值
            tree[node]=tree[leftNode]+tree[rightNode];
        }
    }

    /**
     * 单点修改
     * @param node 当前节点
     * @param start 当前节点对应区间的左边界
     * @param end   当前节点对应区间的右边界
     * @param index 需要更新节点的下标
     * @param val
     */
    public static void updateTree(int node,int start,int end,int index,int val){
        if(start==end){
            arr[index]=val; //修改arr数组的值
            tree[node]=val; //修改线段树中对应节点的值
        }else{
            int mid=(start+end)/2;  //区间一分为二
            int leftNode=2*node+1;
            int rightNode=2*node+2;
            if(index>=start&&index<=mid){   //要修改的值在左子树中
                updateTree(leftNode,start,mid,index,val);
            }else{  //要修改的值在右子树中
                updateTree(rightNode,mid+1,end,index,val);
            }
            //更新父节点的值
            tree[node]=tree[leftNode]+tree[rightNode];
        }
    }

    //区间查询，查询区间[L-R]的和
    public static int queryTree(int node,int start,int end,int L,int R){
       if(R<start||L>end){//查询的区间不在范围之内
           return 0;
       }else if(L<=start&&end<=R){//是否区间覆盖，要查询的区间刚好被包含
           //直接返回tree[node],不用再往下查,tree[node]就是该子区间的和
           return tree[node];
       }else if(start==end){    //一直查到了叶子节点
           return tree[node];
       }else{
           int mid=(start+end)/2;
           int leftNode=2*node+1;
           int rightNode=2*node+2;
           //查询左子树
           int sumLeft = queryTree(leftNode, start, mid, L, R);
           //查询右子树
           int sumRight=queryTree(rightNode,mid+1,end,L,R);
           //将左右子树的结果相加即可
           return sumLeft+sumRight;
       }
    }
}

线段树入门_线段树_27