线段树

线段树 $(\text{Segment Tree})$ ，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。

线段树的思想和分治思想很相像。

线段树的每一个节点都储存着一段区间 $[L…R]$ 的信息，其中叶子节点 $L=R$ 。它的大致思想是：将一段大区间平均地划分成 $2$ 个小区间，每一个小区间都再平均分成 $2$ 个更小区间……以此类推，直到每一个区间的 $L$ 等于 $R$ (这样这个区间仅包含一个节点的信息，无法被划分)。通过对这些区间进行修改、查询，来实现对大区间的修改、查询。

这样一来，每一次修改、查询的时间复杂度都只为 $O(\log _2n)$ 。

但是，可以用线段树维护的问题必须满足区间加法，否则是不可能将大问题划分成子问题来解决的。

---

区间加法

一个问题满足区间加法，仅当对于区间 $[L,R]$ 的问题的答案可以由 $[L,Mid]$ 和 $[mid+1,R]$ 的答案合并得到。
经典的区间加法问题有：

1. 区间求和 $\sum _{i=L} ^R a _i=\sum _{i=L} ^{Mid} a _i+\sum _{i=Mid+1} ^R a _i(L\leq Mid <R)$
2. 区间最值 $\max _{i=L} ^R a _i=\max(\max _{i=L} ^{Mid} a _i,\max _{i=Mid+1} ^R a_i)(L \leq Mid <R)$

不满足区间加法的问题有：

1. 区间的众数
2. 区间的最长不下降子序列

---

原理

线段树主要是把一段大区间平均地划分成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在 $\log$ 级别（因为这棵线段树是平衡的）。也就是说，一个 $[L…R]$ 的区间会被划分成 $[L…Mid]$ 和 $[Mid+1…R]$ 这两个小区间进行维护，直到 $L=R$ 。

下图就是一棵 $[1…10]$ 的线段树的分解过程（相同颜色的节点在同一层）

可以发现，这棵线段树的最大深度不超过 $ [log_2(n−1)]+2
（其中 $[x]$ 表示对 $x$ 进行下取整）。

---

实现

注：所有代码中的 $lson$ 代表 $l,mid,rt<<1$ ， $rson$ 代表 $mid+1,r,rt<<1|1$ 。

存储

线段树的存储有很多种，既可以用数组存，也可以用结构体存，但是线段树的存储原理和堆基本相同,即线段树满足以下几条性质：

1. 编号为 $k$ 的节点的左儿子编号为 $k<< 1$ ，右儿子编号为 $k<<1|1$ ，父节点编号为 k>>1 $ ；（堆的性质）
2. 线段树每个点存储的是一段区间，每次用过调用区间的左右端点来实现操作。

通常线段树每个点存这几个东西：区间左端点，区间右端点，区间特征值，下传标记（后面会讲到）。

我们以求一段区间的和为例：

struct node
{
    int l;//左端点
    int r;//右端点
    int sum;//区间的和
    int lazy;//下传标记（后面会讲到）
}tree[maxn<<2];//开4倍大小

上传状态

假如修改了线段树的子节点，由于其父节点包含这个子节点，所以父节点也要更新，故从当前位置一次向上更新。

void pushup(int rt)//rt表示当前位置
{
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;//父节点的区间和等于其子节点区间和的和
}

初始化

线段树的初始化只用二分向下查找，直到叶结点，查找过程中给当前区间包含的信息赋值即可。

void build(int l,int r,int rt,int val)//l，r代表区间的左右端点，rt代表当前位置，val代表赋的值
{
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r)//找到叶结点
    {
        tree[rt].sum=val;
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1,val);
    build(mid+1,r,rt<<1|1,val);//向下二分查找
    pushup(rt);//上传状态
}

单点修改

当我们要把下标为 $k$ 的数字修改（加减乘除、赋值运算等）时，可以直接在根节点往下 $DFS$ 。如果当前节点的左儿子包含下标为 $k$ 的数（即对于左儿子区间 $L_{lson}…R_{lson},L_{lson}\leq k <R_{rson}$ ），那么就走到左儿子，否则走到右儿子（右儿子一定包含下标为 $k$ 的数，因为根节点一定包含这个数，而从根节点往下走，能到达的点也一定包含这个数），直到 $L=R$ 。这时就走到了只包含 $k$ 的那个节点，只需要把这个点修改即可（这个点就相当于线段树中唯一只储存着 $k$ 的信息的节点）。最后记得在回溯的时候把沿途经过的所有的点的值全部修改一下。

void update(int p,int val,int rt)//p是要修改节点的编号，val是要修改成的值，rt当前节点
{
    if(tree[rt].l==tree[rt].r)//如果当前区间只包含一个元素，那么该元素一定就是我们要修改的。
    {
        tree[rt].sum=val;
        return ;
    }//由于该区间的sum一定等于编号为x的数字，所以直接修改sum就可以了。
    int mid=(tree[rt].l+tree[rt].r)>>1;
   	if(p<=mid)
        update(p,val,rt<<1);
    else
        update(p,val,rt<<1|1);
    pushup(rt);
}

区间修改

其实如果会了单点修改的话，区间修改就不会太难理解了。
区间修改大体可以分为两步：

1. 找到区间中全部都是要修改的点的线段树中的区间
2. 修改这一段区间的所有点

先来解决第一步：
我们先从根节点出发（根节点一定包含所有的点，包括被修改区间），一直往下走，直到当前区间中的元素全部都是被修改元素。
当左区间包含整个被修改区间时，我们就递归到左区间；
当右区间包含整个被修改区间时，我们就递归到右区间；

否则，情况一定就如下图所示：

怎么办？这种情况似乎有些难了。
不过，通过思考，我们可以发现，被修改区间中的元素间，两两之间都不会产生影响。
所以，我们可以把被修改区间分解成两段，使得其中的一段完全在左区间，另一端完全在右区间。
很明显，直接在mid的位置将该区间切开是最好的。如下图所示：

通过一系列的_玄学操作，我们成功地把修改区间分解成一段一段的。但问题来了：我们怎样修改这些区间呢？
最暴力的做法是每一次都像建树一样，遍历区间内的所有节点，一一修改。但是这样的时间复杂度显然 $O(n ^2\log _2 n)$ ，比暴力 $O(n^2)$ 多了个 $\log$ ，我要这线段树有何用？
这里就要引入一样新的神奇的东西——懒惰标记！

懒惰标记

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么（区间求和只用记录有没有被访问过，而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作）
这里再引入两个很重要的东西：相对标记和绝对标记。

---

相对标记和绝对标记

相对标记指的是可以共存的标记，且打标记的顺序与答案无关，即标记可以叠加。 比如说给一段区间中的所有数字都 $+a$ ，我们就可以把标记叠加一下，比如上一次打了一个 $+1$ 的标记，这一次要给这一段区间 $+2$ ，那么就把 $+1$ 的标记变成 $+3$ 。

绝对标记是指不可以共存的标记，每一次都要先把标记下传，再给当前节点打上新的标记。这些标记不能改变次序，否则会出错。 比如说给一段区间的数字重新赋值，或是给一段区间进行多种操作。

---

有了懒惰标记这种神奇的东西，我们区间修改时就可以偷一下懒，先修改当前节点，然后直接把信息挂在节点上就可以了！

如下面这棵线段树，当我们要修改区间 $[1…4]$ ，将元素赋值为 $1$ 时，我们可以先找到所有的整个区间都要被修改的节点，显然是储存区间 $[1…3]$ 和 $[4…4]$ 的这两个节点。我们就可以先把 $[1…3]$ 的 $sum$ 改为 $(3−1+1) \times 1=3$ ，把 $[4…4]$ 的 $sum$ 改为 $(1−1+1)\times 1=1$ 然后给它们打上值为 $1$ 的懒惰标记，然后就可以了。

这样一来，我们每一次修改区间时只要找到目标区间就可以了，不用再向下递归到叶节点。
下面是区间 $+x$ 的代码：

void range_update(int l,int r,int rt,int val)//当前到了编号为rt的节点，要把[l..r]区间中的所有元素的值+val
{
	if(a[rt].l==l&&a[rt].r==r)//如果找到了全部元素都要被修改的区间
	{
		a[rt].sum+=(r-l+1)*x;//更新该区间的sum
		a[rt].lazy+=x;//懒惰标记叠加
         return;
	}
	int mid=(a[rt].l+a[rt].r)>>1;
	if(r<=mid)
        range_update(l,r,rt<<1,val);
	//如果被修改区间完全在左区间
	else if(l>mid)
        range_update(l,r,rt<<1|1,val);
	//如果被修改区间完全在右区间
	else
    {
        range_update(lson,x);
        range_update(rson,x);
    }//如果都不在，就要把修改区间分解成两块，分别往左右区间递归
	pushup(rt);//记得更新点k的值
}

请注意：某些题目的懒惰标记属于绝对标记（如维护区间平方和），一定要先下传标记，再向下递归。

下传标记

碰到相对标记这种容易欺负的小朋友，我们只用打一下懒惰标记就可以了。
但是，遇到绝对标记，或是下文提到的区间查询，简单地打上懒惰标记就明显 $GG$ 了。毕竟，懒惰标记只是简单地在节点挂上一个信息而已，遇到复杂的情况可是不行的啊！
于是，懒惰标记的下传操作就诞生了。
顾名思义，下传标记就是把一个节点的懒惰标记传给它的左右儿子，再把该节点的懒惰标记删去。

我们先来回顾一下标记的含义：

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么。

显然，父区间是包含子区间的，也就是对于父区间的标记和子区间是有联系的。在大多数情况下，父区间和子区间的标记是相同的。因此，我们可以由父区间的标记推算出子区间应当是什么标记。
注意：以下所说的问题都是指区间赋值，除非有什么特别的申明。
如果要给一个节点中的所有元素重新赋值为x，那么它的儿子也必定要被赋值成x。所以，我们直接在子节点处修改sum值，再把子节点的标记改变一下就可以了（由于区间赋值要用绝对标记，因此当子节点已经有标记时，要先下传子节点的标记，再下穿该节点的标记。但是区间赋值会覆盖掉子节点的值，因此在这个问题中，直接修改标记就可以了）

代码如下：

void pushdown(int rt)//将点k的懒惰标记下传
{
	if(a[rt].l==a[rt].r)
    {
        a[rt].lazy=0;
        return;
    }//如果节点k已经是叶节点了，没有子节点，那么标记就不用下传，直接删除就可以了
	a[rt<<1].sum=(a[rt<<1].r-a[rt<<1].l+1)*a[rt].lazy;
	a[rt<<1|1].sum=(a[rt<<1|1].r-a[rt<<1|1].l+1)*a[rt].lazy;//给k的子节点重新赋值
	a[rt<<1].lazy=a[rt<<1|1].lazy=a[rt].lazy;//下传点k的标记
	a[rt].lazy=0;//记得清空点k的标记
}

区间查询

上面我们很轻松地解决了修改的问题，于是我们就维护了一个完整的在线线段树了。但是光有维护是没用的，我们还要处理询问的问题。最常见的莫过于区间查询了，如询问区间[l…r]中所有数的和。
这其实和区间修改是类似的。我们也分类讨论：
当查找区间在当前区间的左子区间时，递归到左子区间；
当查找区间在当前区间的右子区间时，递归到右子区间；
否则，这个区间一定是跨越两个子区间的，我们就把它切成2块，分在两个子区间查询。最后把答案合起来处理就可以了（如查询区间和时就把两块区间的和加起来，查询最大值时就返回两块区间的最大值）
最后强调一个细节：记得在查询之前下传标记！！！

下面贴上查询区间和的代码：

int query(int l,int r,int rt)//当前到了编号为rt的节点，查询[l..r]的和
{
	if(a[rt].l==l&&a[rt].r==r)
        return a[rt].sum;//如果当前区间就是询问区间，完全重合，那么显然可以直接返回
	int mid=(a[rt].l+a[rt].r)>>1;
    if(a[rt].lazy)
        pushdown(rt);//如果当前节点被打上了懒惰标记，那么就把这个标记下传，这一句其实也可以放在下一语句的后面
	if(r<=mid)
        return query(rt<<1,l,r);//如果询问区间包含在左子区间中
	if(l>mid)
        return query(rt<<1|1,l,r);//如果询问区间包含在右子区间中
	return query(lson)+query(rson);//如果询问区间跨越两个子区间
}

扫描线

扫描线，就是一根假想的线，从左到右的一条竖线扫描过去。

扫描线的用途很简单，就是通过算出几何图形中每一条边来得到这个几何图形的面积或者周长。

比如说下面这个图形：

计算这两个矩形的面积等价于计算红色，绿色，蓝色三块的面积的和。

我们用扫描线在竖直方向上扫，为了避免横坐标范围过大，所以先进行离散化。

在进行扫描前。要保存好全部矩形的上边和下边。而且依照它们所处的高度进行排序，另外我们给上边赋值为 $-1$ 。给上边赋值为 $1$ 。接着我们用一个结构体来保存全部矩形的上边和下边，当中还有两条边不用管，由于他们已经包含在了高度中。高度差便能得到边的长度。

然后将扫描线从下往上扫描。每遇到一条上边或者下边就停下来，将这条线段增加到总区间上，下边赋值是 $1$ ，扫描到下边的话相当于往总区间插入一条线段。上边为 $-1$ 。扫描到上边相当于在总区间删除一条线段（也能够理解为当插入 $1$ 的时候我们的扫描线在一个矩形中，当插入 $-1$ 的时候证明我们的扫描线离开了一个矩形的区域，如此能够知道，区间不会出现负数的情况，由于永远都是 $1\geq -1$ ，就是下边大于上边。他们相加是永远大于等于零的）。

然后用下一条边的高度减去当前这条边的高度，乘上总区间被覆盖的长度，就能得到矩形的面积。

来一道板子题：FZOJ1850图形面积

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
long long n;
long long x[201];
struct tree
{
    long long l;//左端点
    long long r;//右端点
    long long h;//高度
    long long mark;//判断上下边的标记
}e[1010];
struct node
{
    long long l;//左端点
    long long r;//右端点
    long long len;//有效覆盖长度
    long long mark;//判断当前区间是否完全被覆盖
}s[1010];
long long cmp(tree a,tree b)
{
    return a.h<b.h;
}
void build(long long l,long long r,long long rt)
{
    s[rt].l=l;
    s[rt].r=r;
    s[rt].len=0;
    s[rt].mark=0;
    if(l==r)
        return ;
    long long mid=(s[rt].l+s[rt].r)>>1;
    build(lson);
    build(rson);
}
void pushup(long long rt)
{
    if(s[rt].mark)
        s[rt].len=x[s[rt].r+1]-x[s[rt].l];
    else if(s[rt].l==s[rt].r)
        s[rt].len=0;
    else
        s[rt].len=s[rt<<1].len+s[rt<<1|1].len;
}
void update(long long l,long long r,long long rt,long long flag)
{
    if(s[rt].l==l&&s[rt].r==r)
    {
        s[rt].mark+=flag;
        pushup(rt);
        return ;
    }
    long long mid=(s[rt].l+s[rt].r)>>1;
    if(r<=mid)
        update(l,r,rt<<1,flag);
    else if(l>mid)
        update(l,r,rt<<1|1,flag);
    else
    {
        update(lson,flag);
        update(rson,flag);
    }
    pushup(rt);
}
int main()
{
    scanf("%lld",&n);
    long long x1,y1,x2,y2;
    long long cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        e[cnt].l=e[cnt+1].l=x1;
        e[cnt].r=e[cnt+1].r=x2;
        e[cnt].h=y1;
        e[cnt+1].h=y2;
        e[cnt].mark=1;
        e[cnt+1].mark=-1;
        x[cnt]=x1;
        x[cnt+1]=x2;
        cnt+=2;
    }
    sort(e,e+cnt,cmp);
    sort(x,x+cnt);
    long long tot=1;
    long long ans=0.0;
    for(int i=1;i<cnt;i++)
        if(x[i]!=x[i-1])
            x[tot++]=x[i];
    build(0,tot-1,1);
    for(int i=0;i<cnt;i++)
    {
        long long l=lower_bound(x,x+tot,e[i].l)-x;
        long long r=lower_bound(x,x+tot,e[i].r)-x-1;
        update(l,r,1,e[i].mark);
        ans+=(e[i+1].h-e[i].h)*s[1].len;
    }
    printf("%lld",ans);
    return 0;
}

动态开点

其实原理很简单，就是什么时候用到这个点再开点，防止一些卡空间的题。

例如我们以 $pushdown$ 操作和 $range _ update$ 为例：

void pushdown(int l,int r,int rt)
{
    if(lazy[rt])
    {
        int mid=(l+r)>>1;
        if(l!=r)
        {                               //不是叶子节点则需要开辟左节点或右节点
            if(s[rt].l==0)
                s[rt].l=++cnt;          //从而把标记传下去
            if(s[rt].r==0)
                s[rt].r=++cnt;
            s[rt<<1].lazy=s[rt].lazy;
            s[rt<<1|1].lazy=s[rt].lazy;
            s[rt<<1].sum=(mid-l+1)*s[rt].lazy;
            s[rt<<1|1].sum=(r-mid)*s[rt].lazy;
        }
        s[rt].lazy=-1;
    }
}

void range_update(int L,int R,int p,int l,int r,int &rt)
{
    if(!rt)
        rt=++cnt;                            //动态开点就是什么时候用什么时候开点
    if(L<=l&&r<=R)
    {
        s[rt].lazy=p;
        s[rt].sum=p*(r-l+1);
        return;
    }
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if(L<=mid)
    	range_update(L,R,p,lson);
    if(R>mid)
    	range_update(L,R,p,rson);
    s[rt].sum=s[rt<<1]+sum[rt<<1|1];
}

权值线段树

权值线段树之所以会带上“权值”二字，是因为它是记录权值的线段树。因此需要用到离散化操作来处理 $a[1…n]$ 。记录权值指的是，每个点上存的是区间内的数字出现的总次数。比如一个长度为 $10$ 的数组 $[1,1,2,3,3,4,4,4,4,5]$ 。

其中 $1$ 出现了两次，那么 $[1,1]$ 这个节点的值为 $2$ ， $2$ 出现了 $1$ 次，那么 $[2,2]$ 这个节点的值为 $1$ ，那么显然 $[1,2]$ 这个节点的值为 $3$ ，即 $1$ 出现的次数和 $2$ 出现的次数加和。那么如果我想要知道这个数组上的第 $k$ 小，我就可以在这棵权值线段树上用 $\log n$ 的时间来实现。比如我想要求这个区间上的第 $7$ 小，那么我先找到这棵树的根节点，根节点上的数字显示的是 $10$ ，表示在 $[1,8]$ 这个区间上一共有 $10$ 个数字，那么我只要去看它的左孩子上的个数是多少。这时我看到左孩子上的数字是 $9$ ，说明前9小的数字都在左子树上，那么我要找的第 $7$ 小也在左子树上，那么我就递归去找左子树。当我再看左孩子的时候，看到数字是 $3$ ，说明前3小的数字在左子树上，那么我要找的就是右子树上的第 $k-s[i].sum$ 小，即 $7-3=4$ ，找到右子树上的第 $4$ 小即可。直到找到某一个叶子节点，说明找到了我要找的第 $k$ 小。这是通过权值线段树找到区间 $[1,n]$ 上的第 $k$ 小/大的应用。

_{其实就相当于一个桶。}

线段树合并

线段树合并，一般来说是与线段树动态开点一起用的，它的作用将两棵线段树所统计的信息整合到一棵线段树上。（由于多棵线段树会导致空间复杂度极高，所以线段树合并一般会与动态开点一起使用）。

线段树通过用并查集的思想合并。

我们在合并线段树的时候，肯定不可能一个点一个点的合并，那么我们就需要将一些无用的合并操作去掉。由于我们是动态开点，那么无用的操作指的就是，两棵线段树中有一棵未开辟的节点（或两棵都未开辟），那么直接返回已经开辟了的那一棵就可以了。

int merge(int x,int y)
{
    if(x==0||y==0)//若这棵线段树还没开辟，直接返回开辟那一棵的节点
        return x+y;//因为其中一棵编号为0，直接用另外一棵加上0就可以了。
    tree[x].l=merge(e[x].l,e[y].l);
    tree[x].r=merge(e[x].r,e[y].r);//合并
    pushup(x);
    return x;
}

一道合并的题FZOJ2048永无乡

#include<stdio.h>
#include<string.h>
#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
struct node
{
    int u;
    int v;
}s[201010];
struct tree
{
    int l;
    int r;
    int sum;
}e[2001010];
int num;
int root[201010];
int rank[201010],w[201010],fa[201010];
int n,m,q,cnt;
int getfa(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=getfa(fa[x]);
}
void pushup(int rt)
{
    e[rt].sum=e[e[rt].l].sum+e[e[rt].r].sum;
}
void add(int l,int r,int &rt,int x)
{
    if(!rt)
        rt=++cnt;
    if(l==r)
    {
        e[rt].sum=1;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
        add(l,mid,e[rt].l,x);
    else
        add(mid+1,r,e[rt].r,x);
    pushup(rt);
}
int query(int l,int r,int rt,int val)
{
    if(l==r)
        return l;
    int mid=(l+r)>>1;
    if(e[e[rt].l].sum>=val)
        return query(l,mid,e[rt].l,val);
    else
        return query(mid+1,r,e[rt].r,val-e[e[rt].l].sum);
}
int merge(int x,int y)
{
    if(x==0||y==0)
        return x+y;
    e[x].l=merge(e[x].l,e[y].l);
    e[x].r=merge(e[x].r,e[y].r);
    pushup(x);
    return x;
}
void Union(int u,int v)
{
    u=getfa(u);
    v=getfa(v);
    if(u==v)
        return ;
    root[u]=merge(root[u],root[v]);
    fa[v]=u;
}
int main()
{
    char s[31];
    int u,v,cnt;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        fa[i]=i;
        rank[w[i]]=i;
    }
    for(int i=1;i<=n;i++)
        add(1,n,root[i],w[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        Union(u,v);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%s",s);
        scanf("%d%d",&u,&v);
        if(s[0]=='B')
            Union(u,v);
        else
        {
            cnt=root[getfa(u)];
            if(e[cnt].sum<v)
                printf("%d\n",-1);
            else
                printf("%d\n",rank[query(1,n,cnt,v)]);
        }
    }
    return 0;
}

资料引用来源

1. “Alexander__菜鸡”大佬线段树详解

2. “Stupid_Turtle”大佬权值线段树、主席树学习

3. “一个不愿透露姓名的OIER”大佬线段树合并的思想和应用

4. “lxjshuju”大佬线段树 + 扫描线加深具体解释

   感谢以上大佬的博客提供知识来源