Segment Tree 线段树算法(java)

这篇具有很好参考价值的文章主要介绍了Segment Tree 线段树算法(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Segment Tree 线段树算法

什么是线段树算法:
线段树(Segment Tree)是一种基于树结构的数据结构,用于解决区间查询问题,例如区间最大值、最小值、区间和等。线段树是一种高度平衡的二叉树,每个节点都代表了一个区间。下面我们来详细了解一下线段树算法。

线段树的构建
线段树的构建过程可以通过递归的方式实现。对于一个给定的数组,我们首先构建一个高度为 log n 的线段树,其中 n 是数组的长度。每个节点都代表了一个区间,例如左儿子节点代表[l, r],右儿子节点代表[r+1, r2]。具体的构建过程如下:
1.初始化根节点,区间为[0, n-1]。
2.对于每个节点,如果它的左右儿子节点存在,就递归构建左右儿子节点。
3.每个节点的值根据需要更新,例如查询最大值时,每个节点存储的值应该是该区间内的最大值
4.当构建到叶子节点时,将叶子节点的值存储为对应区间的值。

线段树查询
线段树查询可以通过递归的方式实现。对于一个查询区间[l, r],我们从根节点开始,根据区间与节点所代表区间的关系,逐步向下遍历子树,直到到达叶子节点。在遍历过程中,我们可以根据需要更新节点的值,例如查询最大值时,如果当前节点的值比查询区间的值更大,就将当前节点的值更新为查询区间的值。具体的查询过程如下:
1.从根节点开始,如果当前节点所代表的区间与查询区间有交集,就继续向下遍历。
2.如果当前节点的左儿子节点存在,并且左儿子节点所代表的区间与查询区间有交集,就递归查询左儿子节点。
3.如果当前节点的右

示例1:
Segment Tree 线段树算法(java),java,算法,数据结构,算法,java,开发语言,数据结构,hash-index 线段树是一种二叉搜索树。他将一段区间划分为若干个单位区间,每个节点之间存储一个区间。思想类似于分治思想。

如图所示,线段树中每一个节点都存储着区间[1,10]中的信息,叶子节点的L = R。大致思想为:将大区间平分为2个小区间,每一个小区间再平分为更小的2个区间,以此类推直到每个区间的L = R,通过对这些区间的修改和查询来实现对大区间的修改和查询。
单点查找、修改的时间复杂度:O(log2n)
线段树维护的问题必须满足区间加法 例如:[1,3] + [2,4] = [1,4]。

代码演示

 public static class SegmentTree{
        //记录原数组的长度, 线段树下标是从1 开始,原数组是从0开始,
        private int MAXN;
        //保存原数组的信息,不过下标从1开始了
        private int[]arr;
        //模拟线段树维护记录区间和
        private int[]sum;
        //为累加和懒加载
        private int[]lazy;
        //区间更新的值
        private int[]change;
        //是否更新的标记
        private boolean[]update;

        public SegmentTree(int[] origin) {
            MAXN = origin.length + 1;
            for (int i = 1; i < MAXN;i++){
                arr[i] = origin[i - 1];
            }
            //用来记录逻辑概念中,某一范围的累加和信息。
            sum = new int[MAXN << 2];
            //用来支持逻辑概念中,某一个范围沒有往下透传的累加任务
            lazy = new int[MAXN << 2];
            //用来支持逻辑概念中,某一个范围更新任务,更新成了什么
            change = new int[MAXN << 2];
            // 用来支持逻辑概念中,某一个范围有没有更新操作的任务
            update = new boolean[MAXN << 2];
        }

        /**
         * rt 代表逻辑概念中 所在的位置
         * @param rt
         */
        public void pushUp(int rt){
            sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
        }

        /**
         * 初始化线段树
         * 初始化时 先把sum数组填好
         * @param l
         * @param r
         * @param rt
         */
        public void build(int l,int r,int rt){
            if (l == r){
                sum[rt] = arr[l];
                return;
            }
            int mid = (r + l) >> 1;
            build(l,mid,rt << 1);
            build(mid + 1,r,rt << 1 | 1);
            pushUp(rt);
        }
        /**
         * 任务往下分配
         * @param rt 当前位置
         * @param ln 分配任务的左边界
         * @param rn 分配任务的右边界
         */
        private void pushDown(int rt,int ln,int rn){
            if (update[rt]){
                update[rt << 1] = true;
                update[rt << 1 | 1] = true;
                change[rt << 1] = change[rt];
                change[rt << 1 | 1] = change[rt];
                lazy[rt << 1] = 0;
                lazy[rt << 1 | 1] = 0;
                sum[rt << 1] = change[rt] * ln;
                sum[rt << 1 | 1] = change[rt] * rn;
                update[rt] = false;
            }
            //懒加载的数据分发下去
            if (lazy[rt] != 0){
                lazy[rt << 1] += lazy[rt];
                sum[rt << 1] += lazy[rt] * ln;
                lazy[rt << 1 | 1] += lazy[rt];
                sum[rt << 1 | 1] += lazy[rt] * rn;
                lazy[rt] = 0;
            }
        }

        /**
         * L - R 任务的范围,C 修改的大小
         * l r ,rt 所负责的范围。
         * @param L
         * @param R
         * @param C
         * @param l
         * @param r
         * @param rt
         */
        public void add(int L,int R,int C,int l,int r,int rt){
            if (L <= l && r <= R){
                sum[rt] += C * (r - l + 1);
                lazy[rt] += C;
                return;
            }
            int mid = (r + l) >> 1;
            //任务没有全包,就下发。
            pushDown(rt,mid - l + 1,r - mid);
            if (L <= mid){
                add(L,R,C,l,mid,rt << 1);
            }
            if (R > mid){
                add(L,R,C,mid + 1,r,rt << 1 | 1);
            }
            pushUp(rt);
        }
       

        /**
         *  //L - R 范围内所有值都变成 C
         *  //l - r 是 rt 所在位置的包含数字的范围
         * @param L
         * @param R
         * @param C
         * @param l
         * @param r
         * @param rt
         */
        public void update(int L,int R,int C,int l,int r,int rt){
            //所在范围被全包了。
            if (L <= l && r <= R){
                change[rt] = C;
                update[rt] = true;
                sum[rt] = (r - l + 1) * C;
                lazy[rt] = 0;
                return ;
            }

            int mid = (r + l) >> 1;
            pushDown(rt,mid - l + 1,r - mid);
            if (L <= mid){
                update(L,R,C,l,mid ,rt << 1);
            }
            if (R > mid){
                update(L,R,C,mid + 1,r,rt << 1 | 1);
            }
            pushUp(rt);
        }

       

        /**
         * 查询
         *  //L - R 要查询的范围
         *   //l - r 是 rt 所包含的范围。
         * @param L
         * @param R
         * @param l
         * @param r
         * @param rt
         * @return
         */
        public long query(int L,int R,int l,int r,int rt){
            if (L <= l && r <= R){
                return sum[rt];
            }
            int mid = (r + l) >> 1;
            pushDown(rt,mid - l + 1,r - mid);
            long ans = 0;
            if (L <= mid){
                ans += query(L,R,l,mid,rt << 1);
            }
            if (R > mid){
                ans += query(L,R,mid + 1, r, rt << 1 | 1);
            }
            return ans;
        }
    }

蓄水池算法

蓄水池算法文章来源地址https://www.toymoban.com/news/detail-586433.html

到了这里,关于Segment Tree 线段树算法(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • 高级数据结构与算法 | 布谷鸟过滤器(Cuckoo Filter):原理、实现、LSM Tree 优化

    如果对布隆过滤器不太了解,可以看看往期博客:海量数据处理(一) :位图与布隆过滤器的概念以及实现 布隆过滤器 局限 对于需要处理海量数据的时候,如果我们需要快速判断一条记录是否,通常会使用过滤器来进行验证,而其中最常见的就是布隆过滤器(Bloom Filter)—

    2024年02月19日
    浏览(49)
  • 【高级数据结构】线段树

    目录 树状数组1(单点修改,区间查询) 树状数组2(区间修改,单点查询) 线段树1(区间修改,区间查询) 代码源线段树1(查询最小值出现次数)  代码源线段树2(最大字段和) 树状数组1(单点修改,区间查询) 题目链接:  https://www.luogu.com.cn/problem/P3374 代码: 树状

    2024年02月15日
    浏览(39)
  • Java学数据结构(3)——树Tree & B树 & 红黑树 & Java标准库中的集合Set与映射Map & 使用多个映射Map的案例

    1.B树,阶M,数据树叶上,根的儿子数在2和M之间,除根外,非树叶节点儿子为M/2和M之间; 2.B树的插入引起分裂,B树的删除,引起合并和领养; 3.红黑树,根是黑的,红色节点的儿子必须是黑的,所有路径的黑色节点数相同; 4.红黑树的插入,颜色翻转,单旋转,插入节点定

    2024年02月11日
    浏览(68)
  • 数据结构:树(Tree)

    树是一种非线性结构,他是由n(n=0)个有限结点组成的一个具有层次关系的集合。 当n=0时,该树为空树。 在任意一个非空树中都满足以下条件: 1、有一个特殊的结点,称为根结点,根结点没有前驱结点 2、当n1时,其他结点可分为M(M0)个互不相交的有限集T1,T2,T3.……、

    2024年01月16日
    浏览(39)
  • 常见的数据结构:树Tree

    目录 1.概念 1.1 满二叉树 1.2 完全二叉树  1.3 平衡二叉树  2.遍历方式 2.1 先序遍历 2.2 中序遍历 2.3 后序遍历 2.4 层序遍历 原理:一种特殊的数据结构,每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子

    2024年02月13日
    浏览(44)
  • Python高级数据结构——树(Tree)

    树是一种非常重要且常用的数据结构,它的层次结构使得在其中存储和检索数据变得高效。在本文中,我们将深入讲解Python中的树,包括树的基本概念、表示方法、常见类型、遍历算法以及实际应用。我们将通过代码示例演示树的操作和应用。 基本概念 树是由节点和边组成

    2024年01月18日
    浏览(42)
  • B_Tree 的数据结构

    头文件(结构体定义与函数声明): 函数实现 (需要在源文件即后缀为.c的文件中实现,否则编译器会报错,重复定义函数): 最后在main源文件中只需要包含该头文件即可使用定义的抽象数据类型: 这里没有提供具体样例,可根据实际情况自行编写。

    2024年01月17日
    浏览(36)
  • 022:vue中tree结构数据变成扁平化table结构数据的示例

    第022个 查看专栏目录: VUE ------ element UI 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 (1)提供vue2的一些基本操作:安装、引用,模板使用,computed,watch,生命周期(beforeCreate,created,beforeMount,mounted, beforeUpdate,upda

    2024年02月12日
    浏览(40)
  • Java 数据结构与算法-树

    树的基础知识 树是算法面试经常遇到的数据结构之一,在实际工作中也有可能经常用到…… 应聘者在准备算法面试时最需要重视的是二叉树…… 二叉树是一种典型的具有递归性质的数据结构。二叉树的根节点可能有子节点,子节点又是对应子树的根节点,它可能也有自己的

    2024年02月08日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包