【讲●解】超全面的线段树：从入门到入坟

(Pre)：其实线段树已经学了很久了，突然想到线段树这个数据结构比较重要吧，想写篇全面的总结，帮助自己复习，同时造福广大(Oier)（~~虽然线段树的思维难度并不高~~）。本篇立志做一篇最浅显易懂，最全面的线段树讲解，采用(lyd)写的《算法竞赛进阶指南》上的顺序，从最基础的线段树到较深入的主席树，本篇均会涉及，并且附有一定量的习题，以后可能会持续更新，那么现在开始吧！

关于作者，，，他咕了。。。。

目录一览

更新日志
线段树想(AC)之基本原理（雾*1
线段树想偷懒之懒标记（雾*2
线段树想应用之扫描线（雾*3
线段树想瘦身之开点与合并（雾*4
线段树想持久之主席树（雾*5
线段树想带修之树套树（雾*6
~~线段树想...不，你不想~~

更新日志

5.19 update：懒标记20%完成。
5.12 update：添加题目链接，~~然后颓去了~~。
5.11 update：修改部分字词，基本原理基本完成，大纲完成。
5.4 update：基本原理20%完成。

线段树想(AC)之基本原理

什么是线段树啊？

首先，你得有树的基本知识。

然后。

以下内容摘自百度百科

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树的一个结点。

很懵？没关系，我们继续。

其实，线段树（(Segment) (Tree)）是一种基于分治思想的二叉树结构，（Q1：为什么一定是二叉？）如果你学过树状数组，你会清楚地知道两者的差异性，并且随着学习的深入，你会发现线段树是一种更为通用的数据结构。

可以说，只要是能满足区间可加性（也就是大区间的信息能由它的两个子区间整理得到）的操作，大都可以用线段树解决。~~有时可能会有一些奇奇怪怪的操作~~。。。

最基本的线段树包含以下几个概念：

线段树每个节点表示一个区间
线段树的唯一根节点表示整个区间统计范围，如[(1,N)]。
线段树的每个叶节点表示一个长度为(1)的元区间，如[(x,x)]。
线段树上的每个节点[(l,r)]，它的左子节点是[(l,mid)]，右子节点是[(mid+1,r)]，其中(mid=(l+r)/2)（这是线段树的标准写法，也有其他不同的写法，但作为初学者，还是从标准入手好）。

如图，这就是一棵线段树。我们可以发现，当整个区间统计长度为(2)的整数次幂时，整棵线段树一定是一棵完全二叉树（Q2：为什么），那我们就可以用堆的编号方法来给线段树来编号啊（其实图中已经编好了）。

即：

根节点编号为(1)。
编号为(x)的节点，它的左儿子编号为(x*2)，右儿子编号为(x*2+1)。

这样，我们就可以用一个数组来存所有节点的编号了！
至于正确性，，，既然你都学到线段树了，那就不用我说了吧。。。

诶等等，那万一整个区间长度不是(2)的整数次幂呢？

看这张图！

可以~~惊讶地~~发现，我们同样可以使用父子二倍标记法。正确性显然，只不过，正是因为这种情况，所以树的最后一层节点编号在数组中的位置可能不是连续的。

如果区间长度为(N)，在最理想的状况下，即(N)是(2)的整数次幂时，(N)个叶节点的满二叉树有(N+N/2+N/4+...+1=2N-1)个节点。只要不是这种情况，那就还有一层，所以我们保存线段树节点编号的数组长度要大于等于(4N)。

于是线段树信息储存如下：

struct SegmentTree {
    int l, r;//每个区间左右端点
    int dat;//区间数据
    //其他一些附加信息
}sak[4*MAX];

当然，线段树的写法多种多样，这是最稳的一种，还有一种是记录左右儿子编号的，后面我们再说，(zkw)线段树就不介绍了吧。。。

建树

我们需要从根节点“(1)”出发，向下递归建树，并把每个节点所代表的区间赋给它。当到达了根节点，便传值，再向上维护信息。

以维护区间和为例，我们可以这样建树：

inline void build(int p, int l, int r) {
    sak[p].l = l, sak[p].r = r;
    if (l == r) {//叶节点赋值
        sak[p].sum = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2*p, l, mid);//递归建左儿子树
    build(2*p + 1, mid + 1, r);//递归建右儿子树
    sak[p].sum = sak[2*p].sum + sak[2*p + 1].sum;//向上传递区间和的信息
}

单点修改

显然，每次操作，我们都需要从根节点开始遍历，递归找到需要修改的叶子节点，然后修改，然后向上传递信息。（Q3：正确性）

inline void change(int p, int x, int val) {
    if (sak[p].l == sak[p].r) { sak[p].sum = val; return; }//找到x位置
    int mid = (l + r) / 2;
    if (x <= mid) change(p*2, x, val)
    else change(p*2+1, x, val);
    sak[p].sum = sak[2*p].sum + sak[2*p + 1].sum;//向上传递区间和的信息

因为整棵树的深度是(logN)，所以单次修改的时间复杂度为(O(logN))。

区间查询

这里直接给出算法过程，正确性显然。

若当前节点所表示的区间已经被询问区间所完全覆盖，则立即回溯，并传回该点的信息。
若当前节点的左儿子所表示的区间已经被询问区间所完全覆盖，就递归访问它的左儿子。
若当前节点的右儿子所表示的区间已经被询问区间所完全覆盖，就递归访问它的右儿子。

以返回区间和为例：

inline ll ask(int p, int l, int r) {
    if (l <= sak[p].l && r >= sak[p].r) {//对应1操作
        return sak[p].sum;
    }
    pushdown(p);
    ll val = 0;
    int mid = (sak[p].l + sak[p].r) / 2;
    if (l <= mid) val += ask(2*p, l, r);//对应2操作
    if (r > mid) val += ask(2*p + 1, l, r);//对应3操作
    return val;	
}

【例题】Can you answer on these queries 3

需要你提供一种数据结构使之能够查询区间最大连续子段和，并且支持单点修改。

让我们来分析一下，在区间上进行操作自然而然可以想到树状数组或者是线段树。这里单点修改好办，难就难在查询上。

想一想怎么办？或者说，我们如何整理子区间的信息？

仔细思考后，我们会发现，一个区间上的连续最大和只有几种情况：

连续最大和的区间只在左儿子所对应的区间上。
连续最大和的区间只在右儿子所对应的区间上。
连续最大和的区间横跨左右儿子的区间。

(1)和(2)这两种情况好弄，直接继承取最值，可情况(3)呢？

除了维护区间和，区间最大连续子段和，我们还需维护紧靠左端的最大连续子段和，以及紧靠右端的最大连续子段和。

于是每次更新时，我们就可以用子区间的信息来更新当前区间了。

具体代码其他的博客也有介绍，但最好自己想一想，我就不打了，~~因为懒~~，思维懂了，代码就来了。

【习题】Interval GCD

题目大意：需要提供一种数据结构使之能够查询区间gcd，并且支持区间加法。

题解：咕咕咕中。。。

Q&A：

A1：既然你都看到这里了，就不用我说了吧。
A2：画个图再(YY)一下，无需多说。
A3：修改的节点只包含在递归时经过的区间中，所以只会对递归时经过的区间产生影响。

线段树想偷懒之懒标记

【引题】A Simple Problem with Intergers

就是叫你实现区间修改，区间查询嘛。

考虑之前讲到的线段树。如果用线段树的单点修改，我们需要先改变叶子节点的值，然后不断地向上递归修改祖先节点直至到达根节点，时间复杂度最高可以到达(O(nlogn))的级别，这还是单次操作，更别说有(10^5)次指令了。。。

现在思考，该怎么办呢？

我们想，如果已经到达了属于答案区间范围内的节点，我们就直接对该节点进行一系列的操作，然后直接返回。这样，一定能保证本次区间更新的正确性。(很显然啊)，可我们知道，区间更新不只一次，如果照刚刚那样更新而不进行任何后处理的话，那么该节点的子节点都未更新，势必会导致答案错误。于是，我们需要一种东西来记录下节点的更新信息，以便下次更新时处理。

我们考虑引入一个名叫(lazytag)（懒标记）的东西——之所以称其为(lazytag)，是因为当我们引入懒标记后，我们不会去更新已经覆盖答案区间的子节点，只有在接下来的操作中我们才可能会用到该区间的子区间。所以这次操作就无需更新。区间更新的期望复杂度就降到了(O(logn))的级别。(感性理解下)

那如何实现呢？

我们思考前面大家做题遇到的(pushup)，（没用过的可以去刷刷前面的题了）它的实质是在线段树中向上传递信息，放在递归之后，那我们要做到(pushdown)，不就是在线段树中从上往下传递信息吗？那就把(pushdown)直接放在每次递归之前就行了啊。

于是，我们就可以如此标记。

inline void change(int p, int l, int r, int d) {
    if (l <= sak[p].l && r >= sak[p].r) {
        sak[p].sum += (ll)d*(sak[p].r - sak[p].l+1);
        sak[p].add += d;
        return;
    }
    pushdown(p);
    int mid = (sak[p].l + sak[p].r) / 2;
    if (l <= mid) change(2*p, l, r, d);
    if (r > mid) change(2*p + 1, l, r, d);
    sak[p].sum = sak[2*p].sum + sak[2*p + 1].sum;	
}