最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 线段树入门解析

    一.基本概念

    1.线段树是一颗二叉树,它储存的是一个区间的信息,比如区间和;

    2.每个节点储存的是这个区间要维护的信息;

    3.线段树基本思想:分治思想;

     

    二.线段树的基本操作

    例题:

    洛谷3372 线段树1

    题目描述

    如题,已知一个数列,你需要进行下面两种操作:

    1. 将某区间每一个数加上 k

    2. 求出某区间每一个数的和。

    输入格式

    第一行包含两个整数 n, m,分别表示该数列数字的个数和操作的总个数。

    第二行包含 n个用空格分隔的整数,其中第 i个数字表示数列第 i项的初始值。

    接下来 m行每行包含 3或 4个整数,表示一个操作,具体如下:

    1. x y k:将区间 [x, y]内每个数加上 k

    2. x y:输出区间 [x, y]内每个数的和。

    输出格式

    输出包含若干行整数,即为所有操作 2 的结果。

    以下线段树的具体实现:

    1. 建树

    主要思路:当前节点为叶子节点时,存储维护的信息

    否则向下递归建立左儿子和右儿子,再将信息合并

    代码:

    注意:

    .tree数组要开四倍空间,因为不一定是完全二叉树

    .不要漏掉return,因为到了叶子节点递归就停止了

    2. 区间查询

      线段树的区间查询一共分三种情况:令目前查询的区间为(l,r),目标区间为(L,R)

    ①:当前查询的区间完全包含在目标区间内(l>=L&&r<=R),直接返回区间l、r的值。

    ②:当前区间不包含在目标区间内(l>R||r<L),直接结束并返回0。

    ③:当前区间部分包含在目标区间内,遍历它的左儿子和右儿子,将得到的结果合并,返回。

    每次修改将当前区间设置为(1,n),再进行查找。

    代码:

    3. 区间修改

    前置:单点修改

    单点修改也是从区间1-n开始,如果要修改的点在当前区间内就遍历左右儿子并修改,如果是叶子节点就修改并返回,算法复杂度O(log n)。

    如果区间修改也像单点修改一样操作,那就会T到飞起,因为数据范围中m、n<=1e5,如果他每次都故意让你更新1-n,那么操作次数会大大超出限制,因此我们要想办法优化。

    我们可以注意到,如果在修改完这个区间后又没有查询到它,那就白白浪费了时间。所以我们要开一个延迟标记(lazy)数组,存储这个区间应该修改的值。如果没有查询到就不动,在查询需要这个区间时再将它传给左右儿子,在修改时则在延迟标记数组上叠加,这样可以减少许多不必要的操作,大大优化时间复杂度。

    代码:

     

    注意:在标记下传后一定要把标记清零,否则会导致重复计算 WA。

    完整代码:

     

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 线段树入门解析

    发表评论

    • 52会员总数(位)
    • 320资源总数(个)
    • 25本周发布(个)
    • 3 今日发布(个)
    • 333稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情