线段树

介绍一下

又是一个倍增思想下奇奇怪怪的东西。

线段树是一种高效维护(在手不残的前提下)区间信息的数据结构，可以在$O(\log{n})$​​​​时间复杂度内实现单点修改、区间修改、区间查询等(各种稀奇古怪的)操作。树状数组能够解决的问题理论上(注意空间复杂度)都可以用线段树解决。就是慢了点，空间占得大了点儿

线段树以树形(满二叉树，二叉搜索树)结构维护着这样一些“线段”(区间)的信息：

• 根结点对应一条$1\sim n$​的线段。
• 任何线段$(l\sim r)$​​​长度$>1$​​​的结点都有恰好两个子结点，分别对应线段 $l\sim mid$​​​ 与 $mid+1\sim r$​​​，其中 $mid=\lfloor\dfrac{l+r}{2}\rfloor$​​​。

线段树上结点的深度每增大 $1$，线段长度就折半，因此线段树深度为 $\log{n}$​​，由此保证了单点修改复杂度为$O(\log{n})$​。

对于任意区间，都可以在线段树上找到不重叠的至多 $2\times\log{n}$​ 条线段（每种深度至多两条）将其恰好覆盖，这保证了线段树区间操作复杂度为 $O(\log{n})$​。

规定根结点编号为 $1$​​​​​​，编号为 $i$​​​​​​ 的结点的两个子结点（若存在）编号为 $2i$​ ​​​​​与 $2i+1$ ​​​​​​。这样定义的结点编号最大不会超过 $4n$​​​​​。

一棵维护最小值的线段树大概长这样：

线段树所占空间的计算

这一段不看不会也罢，只需要记住开 $4n$​ 个数组就行了。

关于线段树的空间：如果采用堆式存储(大部分)($2i$​​是 $i$​​的左儿子，$2i+1$​​是 $i$​​的右儿子)，若有 $n$​​ 个叶子结点，则 $d$​​ 数组的范围最大为 $2^{\lceil\log{n}\rceil+1}$​。 分析：容易知道线段树的深度是 $\lceil\log{n}\rceil$​的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 $2^{\lceil\log{n}\rceil}$​个，又由于其为一棵完全二叉树(补齐未使用节点)，则其总节点个数 $2^{\lceil\log{n}\rceil+1}-1$​。当然如果你懒得计算的话可以直接把数组长度设为 $4n$​，因为 $\dfrac{2^{\lceil\log{n}\rceil+1}-1}{n}$​的最大值在 $n=2^x+1(x\in N_+)$​时取到，此时节点数为 $2^{\lceil\log{n}\rceil+1}-1=2^{x+2}-1=4n-5$​。

正题来了

其实，没啥好说的，很好理解，很不好背……

下面这4个函数，构建了最最最简单的线段树，效果大概可树状数组一样。

ps：变量名尽量统一，好处多多。

宏定义

有效降低代码长度、出错概率以及Debug时间。

如果你很猛，请跳过这一段……

使用位运算是因为本来线段树就很慢，所以要用快一点的位运算

#define Mid ((l + r) >> 1)    //位运算,相当于(l + r)/2
#define Len (r - l + 1)       //区间长度,注意+1
#define Root 1, 1, n          //根节点调用
#define Lpos pos << 1         //左儿子节点编号,相当于pos*2
#define Rpos Lpos | 1         //右儿子节点编号,相当于Lpos+1
#define Lson Lpos, l, Mid     //左儿子调用
#define Rson Rpos, Mid + 1, r //右儿子调用
#define This pos, l, r        //当前节点调用

update函数

更新节点信息

视维护啥而定

for example:

inline void upd(int pos)
{
    tree[pos] = tree[Lpos] + tree[Rpos];          //维护区间和
    tree[pos] = std::max(tree[Lpos], tree[Rpos]); //维护区间最大值
}

build函数

从原数组构建线段树

inline void build(int pos, int l, int r)//pos当前节点编号，l区间右端点，r区间左端点
{
    if (l == r)//区间长度为1则赋值原数组
        tree[pos] = in[l];//注意是l而不是pos，是区间在原数组中维护的位置而不是节点编号
    else
    {
        build(Lson);//递归建树
        build(Rson);
        upd(pos);//更新当前节点信息
    }
}

change_point函数

单点修改线段树上某一位的值

void cpit(int pos, int l, int r, int point, int val) //pos当前节点编号，l右端点，r左端点，point修改目标编号，val修改值
{
    if (l == r) //区间长度为1，进行修改，结束递归
    {
        tree[pos] = val; //根据题意自行更改
        return;
    }
    if (point <= Mid) //如果区间包含左儿子，递归更改
        cpit(Lson, point, val);
    else //如果区间包含右儿子，递归更改
        cpit(Rson, point, val);
    upd(pos); //更新当前节点信息
}

check_block函数

区间(和、最大值等)查询

inline int fblk(int pos, int l, int r, int L, int R) //pos当前节点编号，l右端点，r左端点，L查询区间左端点，R查询区间右端点
{
    if (L <= l && R >= r) //当前线段树上的线段被查询区间完全包含，返回当前线段维护的信息
    {
        return tree[pos];
    }
    stg(This);    //下放当前线段的标记
    if (R <= Mid) //只包含左儿子，递归查找左儿子，直到被查询线段全部被包含
        return fblk(Lson, L, R);
    if (L > Mid) //只包含右儿子，递归查找右儿子，直到被查询线段全部被包含
        return fblk(Rson, L, R);
    return fblk(Lson, L, R) + fblk(Rson, L, R); //左右儿子均含有被查询区间，则同时查找两个儿子
}

“懒”标记

区间 $[l,r]$时，如果修改所有与 $[l,r]$相关的线段，那么时间复杂度将退化为 $O(n)$​。那还不如不写

线段树通过引入懒标记把对整条线段的修改操作暂存在结点上，当需要访问子节点时再把修改操作应用到子结点上。

真理：人类因懒而进步

针对于每个节点开一个(可能不止)标记位，注意数组长度仍为 $4n$。

• 维护多个标记时注意下放的顺序，保证先下放的标记不影响后下放的标记。

​ **例：**同时维护加法标记和乘法标记时，应先下放乘法标记，再下放加法标记。

• 标记累加时注意其正确性，包括是否要改变其他标记。

​ **例：**乘法标记叠加时，加法标记也应乘相应修改值。

get_tag函数

打标签

inline void gtg(int pos, int l, int r, int val) //pos当前节点编号，l右端点，r左端点，val增加量
{
    tag[pos] += val;        //标签累加
    tree[pos] += Len * val; //维护区间和，总增加量=单点增加量*区间长度
}

send_tag函数

将标签下方给两个儿子

inline void stg(int pos, int l, int r) //pos当前节点编号，l右端点，r左端点
{
    gtg(Lson, tag[pos]); //把标签下放给左儿子
    gtg(Rson, tag[pos]); //把标签下放给右儿子
    tag[pos] = 0;        //将pos位标签置0(标签以下放给儿子)
}

change_block函数

区间修改

inline void cblk(int pos, int l, int r, int L, int R, int val) //pos当前节点编号，l右端点，r左端点，L修改区间左端点，R右端点，val修改值
{
    if (L <= l && R >= r) //当前线段树上的线段被查询区间完全包含，打标记
    {
        gtg(This, val);
        return;
    }
    stg(This);    //若两个儿子只有一个被包含，则下方当前线段标记，更新包含修改区间的儿子
    if (L <= Mid) //只包含左儿子，递归查找左儿子，直到被修改线段全部被包含
        cblk(Lson, L, R, val);
    if (R > Mid) //只包含右儿子，递归查找右儿子，直到被修改线段全部被包含
        cblk(Rson, L, R, val);
    upd(pos); //更新当前节点信息
}

维护一些奇奇怪怪的东西

单表一些你想也想不到的烂七八糟的用线段树维护的东西。

• 区间最大子段和

  1. 最大子段

  2. 最大前缀

  3. 最大后缀

• 序列操作

  1. 归零标记

  2. 取反标记

  3. 区间和

  4. 连续前缀0或1个数

  5. 连续后缀0或1个数

• ………………………………

怎么样，意想不到吧

为了方便，毕竟谁也不想写 $5、6$ 个update函数去逐一维护。

所以，C++的高级语法 bulingbuling 的出现了。—————-> struck结构体 + operator运算符重载

使用结构体记录所有需要维护的信息并通过 operator + 实现合并能够有效降低代码难度：

空间的一点儿优化——动态开点线段树

引子

还是先搞一个非常形象的小故事吧。

​ 首先，你想象自己是一位古代的帝王；你精力旺盛，辛勤耕耘20余年，终于在后宫三千佳丽的帮助下，成功为人类的繁衍生息做出了巨大的贡献。

​ 那么，问题来了。你的儿子女儿加在一起已经快赶上一个师~~(手动狗头)~~的规模了，而恰好你现在手里没有钱(你并不被允许使用那么多内存)，不可能让你的所有子女都住上气派辉煌的宫殿，其中大部分不受宠的就只能住在一些破旧的偏殿里(你在自己的机器中能申请到内存)。

​ 现在，另一个国家的元首(评测机)来你国访问，你开始炫耀起你对人类所做出的贡献。这时候，正是展现国家经济军事实力、皇帝大臣精神面貌的时候，你当然不能让来访的外国人知道你手里没钱，连自己子女的房子都四处漏风，否则对方就会认为你好欺负，来攻打你(评测机返回MLE，把你的分数打掉)。

​ 所以，你想到了一个损招：当且仅当你要展示第 $i$ 个儿子时，才把他的房子装修一下，搞好一点，装装样子。至于那些对方看不见的，就爱咋咋地。因为对方时间有限，并不会跟着你看很多的子女(然而仅有的几个住在好地方的又不够展现帝国雄风)，走访的并不会太多，因此并不需要改造太多，国家这点钱还是出得起的(你并没有MLE，骗过了评测机，评测机认为你并不好惹，给了你AC)。

该正经了

当需要维护的区间很长(如 $n=10^9$)但操作次数有限(如 $m=10^5$​)时，如果建立出完整的线段树，空间复杂度为 $O(n)$，无法接受。

但可以发现每次操作涉及到的线段数为 $O(\log{n})$级别，完成所有操作涉及到的区间个数级别为 $O(m\space\log{n})$，这是可以接受的空间开销。

于是我们放弃之前用数组存储线段树上所有结点的做法，而是在访问到未创建结点时为其分配存储位置，这样的线段树叫做动态开点线段树。

线段树上二分

~~与树状数组上二分类似，~~线段树上也可以进行二分。概括地说，线段树上二分的实质是利用线段树上当前结点及其两个子节点维护的信息快速判断要查找的位置在左右哪个区间中。由于线段树的深度为 $\log{n}$，所以线段树上二分的复杂度为 $O(\log{n})$。

权值线段树

与树状数组维护可重集合的 count 数组类似，线段树也可以用来维护可重集合的 count 数组，这样的线段树常被称作权值线段树。在使用动态开点线段树实现权值线段树时可以放松对权值值域的限制（权值甚至可以取为负数！），这与处理较大权值时需要事先离散化的树状数组相比具有巨大的优势。

线段树优化建图

总结

在更多更灵活的题目中，线段树等数据结构往往被用来快速维护一些区间信息，即一种优化暴力的手段。

这一类问题中，数据结构的维护只是最后一步，难点往往在于想出第一步的 $O(n^2)$或 $O(nm)$的暴力。

解决这类优化问题时，一般都是在得到暴力解法后，将要实现的操作都列出来，再选择合适的数据结构维护这些操作。

考场上遇到这类题目一定要先写出暴力，拿到尽可能多的分数！！

md要是遇到线段树的题，一首《凉凉》送给头秃的自己