0x43 线段树

线段树（Segment Tree）是一种基于分治思想的二叉树结构，用于在区间进行信息统计。与按照二进制位（2的次幂）进行区间划分的树状数组相比，线段树是一种更加通用的结构：

1.线段树的每个节点都代表一个区间。

2.线段树具有唯一的根节点，代表的区间是整个统计范围，如$[1,N]$。

3.线段树的每个叶节点都代表一个长度为1的元区间$[x,x]$。

4.对于每个内部节点$[l,r]$，它的左子节点是$[l,mid]$，右子节点是$[mid+1,r]$，其中$mid=(l+r)/2$（向下取整）。

上图展示了一棵线段树。可以发现，除去数的最后一层，整棵线段树一定是一棵完全二叉树，树的深度为$O(logN)$。因此，我们可以按照与二叉堆类似的“父子2倍”节点编号方法：

1.根节点编号为1。

2.编号为$x$的节点的左子节点编号为$x\ast 2$，左子节点编号为$x\ast 2+1$。

这样一来，我们就能简单的使用一个$struct$数组来保存线段树。当然树的最后一层节点在数组中保存的位置是不连续的，直接空出数组中多余的位置即可。在理想情况下，$N$个节点的满二叉树有$N+N/2+N/4+...+2+1=2N-1$个节点。因为在上述储存方式下，最后还有一层产生了空余，所以保存线段树的数组长度要不小于$4N$才能保证不会越界。

线段树的建树

线段树的基本用途是对序列进行维护，支持查询和修改指令。给定一个长度为$N$的序列$A$，我们可以在区间$[1,N]$上建立一棵线段树，每个叶节点$[i,i]$保存$A[i]$的值。线段树的二叉树结构可以很方便地从下往上传递信息。以区间最大值问题为例，记$dat(l,r)$等于 m a x l ≤ i ≤ r { A [ i ] } max_{l\leq i \leq r} \{ A[i]\} maxl≤i≤r​{A[i]}，显然$dat(l,r)=max(dat(l,mid),dat(mid+1,r))$。

下面这段代码建立了一棵线段树并在每个节点上保存了对于区间的最大值。

struct SegmentTree{
    int l,r;
    int dat;
}t[SIZE*4];  //struct数组存储线段树

void build(int p,int l,int r)
{
    t[p].l=l,t[p].r=r; //节点p代表区间[l,r]
    if(l==r) //叶节点
    {
        t[p].dat=a[l];
        return;
	}
    int mid=(l+r)/2;
    build(p*2,l,mid);     //左子节点[l,mid]，编号p*2
    build(p*2+1,mid+1,r); //右子节点[mid+1,r]，编号p*2+1
    t[p].dat=max(t[p*2].dat,t[p*2+1].dat); //从下往上传递信息
}

线段树的单点修改

单点修改是一条形如“C x v”的指令，表示把$A[x]$的值修改为$v$。

在线段树中根节点（编号为1的节点）是执行各种指令的入口。我们需要从根节点出发，递归找到代表区间$[x,x]$的叶节点，然后从下往上更新$[x,x]$以及它的所有祖先节点上保存的信息，如下图所示。时间复杂度为$O(logN)$。

void change(int p,int x,int v)
{
    if(t[p].l==t[p].r)
    {
        t[p].dat=v;
        return;
	}
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
        change(p*2,x,v);
   	else
        change(p*2+1,x,v);
   	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}

线段树的区间查询

区间查询是一条形如“Q l r”的指令，例如查询序列$A$在区间$[l,r]$上的最大值，即 m a x l ≤ i ≤ r { A [ i ] } max_{l\leq i \leq r} \{A[i]\} maxl≤i≤r​{A[i]}。我们只需要从根节点开始，递归执行一下过程：

1.若$[l,r]$完全覆盖了当前节点代表的区间，则立即回溯，并且该节点的$dat$值为候选答案。

2.若左子节点与$[l,r]$有重叠部分，则递归访问左子节点。

3.若右子节点与$[l,r]$有重叠部分，则递归访问右子节点。

int ask(int p,int l,int r)
{
    if(l<=t[p].l&&r>=t[p].r)
        return t[p].dat;  //完全包含
    int mid=(t[p].l+t[p].r)/2;
    int val=-(1<<30); //负无穷大
    if(l<=mid)
        val=max(val,ask(p*2,l,r)); //左子节点有重叠
    if(r>mid)
        val=max(val,ask(p*2+1,l,r)); //右子节点有重叠
    return val;
}
cout<<ask(1,l,r)<<endl;  //调用入口

该查询过程会把询问区间$[l,r]$在线段树上分成$O(logN)$个节点，取它们的最大值作为答案。为什么是$O(logN)$个呢？在每个节点$[p_l,p_r]$上，设$mid=(p_l+p_r)/2$（向下取整），可能会出现一下几种情况：

1.$l\le p_l\le p_r\le r$，即完全覆盖了当前节点，直接返回。

2.$p_l\le l\le p_r\le r$，即只有$l$处于节点之内。

（1）$l>mid$，只会递归右子树。

（2）$l\le mid$，虽然递归两棵子树，但是右子节点会在递归后直接返回。

3.$l\le p_l\le r\le p_r$，即只有$r$位于节点之内，与情况2类似。

4.$p_l\le l\le r\le p_r$，即$l$与$r$都位于节点之内。

（1）$l,r$都位于$mid$一侧，只会递归一棵子树。

（2）$l,r$分别位于$mid$两侧，递归左右两棵子树。

也就是说，只有情况4（2）会真正产生对左右两棵子树的递归。这种情况至多产生一次，之后在子节点上就会变成情况2或3。因此，上述查询过程的时间复杂度为$O(2logN)=O(logN)$。

至此，线段树已经能像0x06节的ST算法一样处理区间最值问题，并且还支持动态修改某个数的值。同时，线段树也已经能支持上一节树状数组的单点增加与查询前缀和指令。

1.延迟标记（懒标记）

在线段树的“区间查询“指令中，每当遇到被询问区间$[l,r]$完全覆盖的节点时，可以立即把该节点上储存的信息作为候选答案返回。我们已经证明，被询问区间$[l,r]$在线段树上会被分成$O(logN)$个小区间（节点），从而在$O(logN)$的时间内求出答案。不过，在”区间修改“指令中，如果每个节点被修改区间$[l,r]$完全覆盖，那么以该节点为根的整棵子树的所有节点储存的信息都会发生变化，若逐一更新，将使得一次区间修改指令的时间复杂度增加到$O(N)$，这是我们不能接受的。

如果我们在一次修改指令中发现节点$p$代表的区间$[p_l,p_r]$被修改区间$[l,r]$完全覆盖，并逐一更新了子树$p$的所有节点，但是之后的查询指令中却完全没有用到$[l,r]$的子区间作为候选答案，那么更新$p$的整棵子树就是徒劳的。

换言之，我们在执行修改指令时，同样可以在$l\le p_l\le p_r\le r$的情况下立即返回，只不过在回溯之前箱节点$p$增加一个标记，标识“该节点曾经被修改，但其子节点尚未被更新”。

如果在后续的指令中，需要从节点$p$向下递归，我们检查$p$是否具有标记。若有标记，就根据标记信息更新$p$的两个子节点，同时为$p$的两个子节点增加标记，然后清除$p$的标记。

也就是说，除了在修改指令中直接划分成的$O(logN)$个节点之外，对任意节点的修改都延迟到“在后续操作中递归进入它的父节点时”再执行。这样一来，每条查询或修改指令的时间复杂度都降低到了$O(logN)$。这些标记被称为“延迟标记”。延迟标记提供了线段树从上往下传递信息的方式。这种“延迟”也是设计算法与解决问题的一个重要思路。

上一节0x42节树状数组中，我们解决了数字序列区间增长和区间查询和的问题，我们也可以利用线段树的延迟标记来解决，这里多了一个$spread$函数实现了延迟标记的向下传递。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N, Q;
int a[100005];
struct SegmentTree
{
    int l, r;
    ll sum, add;
} t[400005];

void build(int p, int l, int r)
{
    t[p].l = l, t[p].r = r;
    if (l == r)
    {
        t[p].sum = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].sum = t[p * 2].sum + t[2 * p + 1].sum;
}

void spread(int p)
{
    if (t[p].add)
    {
        t[p * 2].sum += (ll)(t[p * 2].r - t[p * 2].l + 1) * t[p].add;
        t[p * 2].add += t[p].add;
        t[p * 2 + 1].sum += (ll)(t[p * 2 + 1].r - t[p * 2 + 1].l + 1) * t[p].add;
        t[p * 2 + 1].add += t[p].add;
        t[p].add = 0;
    }
}

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

ll ask(int p, int l, int r)
{
    if (t[p].l >= l && t[p].r <= r)
        return t[p].sum;
    spread(p);
    int mid = (t[p].l + t[p].r) / 2;
    ll ans = 0;
    if (l <= mid)
        ans += ask(p * 2, l, r);
    if (r > mid)
        ans += ask(p * 2 + 1, l, r);
    return ans;
}

int main()
{
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &a[i]);
    build(1, 1, N);
    char op;
    int a, b, c;
    while (Q--)
    {
        cin >> op;
        if (op == 'Q')
        {
            scanf("%d%d", &a, &b);
            printf("%lld\n", ask(1, a, b));
        }
        else
        {
            scanf("%d%d%d", &a, &b, &c);
            change(1, a, b, c);
        }
    }
    return 0;
}

需要指出的是延迟标记的含义是“该节点曾经被修改，但其子节点尚未被更新”，即延迟标记标识的是子节点等待更新的情况。因此，一个子节点被打上“延迟标记”的同时，它保存的信息应该被修改完毕。在编写代码时，一定要注意“更新信息”与“打标记”之间的关系，避免出现错误。

2.扫描线

给定平面直角坐标系中的$N$个矩形，求它们的面积并，即这些矩形的并集在坐标系中覆盖的总面积，如下图所示。

如果我们用一根竖直直线从左往右扫过整个坐标系，那么直线上被并集图形覆盖的长度只会在每个矩形的左右边界处发生变化。

换言之，整个并集图形可以被分成$2\ast N$段，每一段在直线上覆盖的长度（记为$L$）是固定的，因此该段的面积就是$L\ast$该段的宽度，各段面积之和即为所求。这条直线就称为扫描线，这种解题思路被称为扫描线法。

具体来说，我们可以取出$N$个矩形的左右边界。若一个矩形的两个对角顶点坐标为$(x_1,y_1)$和$(x_2,y_2)$，不妨设$x_1<x_2,y_1<y_2$，则左边界记为四元组$(x_1,y_1,y_2,1)$，右边界记为四元组$(x_2,y_1,y_2,-1)$。把这$2N$个四元组按照$x$递增排序，如下图所示。

注意到本题中的$y$坐标范围较大且不一定是整数，我们先把输入的数据中出现的所有$y$坐标放入一个数组，排序、去重，完成离散化。设$val(y)$表示$y$被离散化之后映射到的整数值，$raw(i)$表示整数值$i$对应的原始$y$坐标值。

在离散化后，若有$M$个不同的$y$坐标值，分别对应$raw(1),raw(2),...,raw(M)$，则扫描线至多被分成$M-1$段，其中第$i$段为区间$[raw(i),raw(i+1)]$。建立数组$c$，用$c[i]$记录扫描线上第$i$段被覆盖的次数。起初$c$数组中的元素全为0。

逐一扫描排序后的$2N$个四元组，设当前四元组为$(x,y_1,y_2,k)$。我们把数组$c$中$c[val(y_1)],c[val(y_1)+1],...,c[val(y_2)-1]$把这些值都加上$k$，相当于覆盖了$[y_1,y_2]$这个区间。此时，如果下一个四元组的横坐标为$x_2$，则扫描线从$x$扫到$x_2$的过程中，被覆盖的长度就固定为${\sum }_{c[i]>0}(raw(i+1)-raw(i))$，即数组$c$中至少被覆盖一次的“段”的总长度。于是，我们就让最终的答案$ans$累加上$(x_2-x)\ast {\sum }_{c[i]>0}(raw(i+1)-raw(i))$。

对于每个四元组，采用朴素算法在$c$数组上执行修改与统计，即可在$O(N^2)$的时间内求出并集图形的面积。

我们可以用线段树维护$c$数组，把算法优化到$O(NlogN)$。

本题中，我们只关心整个扫描线（线段树根节点）上被矩形覆盖的长度。而且，因为四元组$(x,y_1,y_2,1)$和$(x,y_1,y_2,-1)$成对出现，所以线段树区间修改也是成对出现的。在这种特殊情形下，我们没有必要下传延迟标记，可以采用更为简单的做法。

除左右端点$l,r$之外，在线段树的每个节点上维护两个值：该节点代表的区间被矩形覆盖的长度$len$，该节点自身被覆盖的次数$cnt$。最初，两者均为0。

对于一个四元组$(x,y_1,y_2,k)$，我们在$[val(y_1),val(y_2)-1]$上执行区间修改。该区间被线段树划分成$O(logN)$个节点，我们把这些节点的$cnt$都加$k$。

对于线段树中任意一个节点$[l,r]$，若$cnt>0$，则$len$等于$raw(r+1)-raw(l)$。否则，该点$len$等于两个子节点的$len$之和。在一个节点的$cnt$值被修改，以及线段树从下往上传递信息时，我们都按照该方法更新$len$值。根节点的$len$值就是整个扫描线上被覆盖的长度。

因为在扫入四元组$(x,y_1,y_2,1)$后进行区间修改$change$操作，被分成的$logN$个区间$cnt$值加1，如果没有扫入四元组$(x,y_1,y_2,-1)$则这被分成的$logN$个区间$cnt$值不可能为0（就算扫入其他出边，之前也扫入了对应的入边，所以这被分成的$logN$个区间$cnt$值不可能为0），只有当扫入对应的四元组$(x,y_1,y_2,-1)$，这被分成的$logN$个区间$cnt$值才可能为0。所以按照上述方法修改，而不使用延迟修改是行得通的。

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define l(p) t[p].l
#define r(p) t[p].r
#define ls (p<<1)
#define rs (p<<1|1)
const int SIZE=1e5;
int N,M,now;
double a[2*SIZE],b[2*SIZE];
struct Line{
    double x,y1,y2;
    int k;
    bool operator<(const Line b)const{
        return x<b.x;
    }
}line[2*SIZE];
struct SegmentTree{
    int l,r;
    int cnt;
    double len;
}t[8*SIZE];

void build(int p,int l,int r)
{
    l(p)=l,r(p)=r;
    if(l==r)
    {
        t[p].cnt=0;
        t[p].len=0;
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[p].cnt=0;
    t[p].len=0;
}

void pushup(int p)
{
    if(t[p].cnt>0)
        t[p].len=b[r(p)+1]-b[l(p)];
    else
    {
        if(l(p)!=r(p))
            t[p].len=t[ls].len+t[rs].len;
        else
            t[p].len=0;
    }
}

void change(int p,int l,int r,int k)
{
    if(l(p)>=l&&r(p)<=r)
    {
        t[p].cnt+=k;
        pushup(p);
        return;
    }
    int mid=(l(p)+r(p))/2;
    if(l<=mid)
        change(ls,l,r,k);
    if(r>mid)
        change(rs,l,r,k);
    pushup(p);
}

int main()
{
    while(scanf("%d",&N)&&N)
    {
        now++;
        M=0;
        double x1,y1,x2,y2;
        for(int i=1;i<=N;++i)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[i*2-1].x=x1,line[i*2-1].y1=y1,line[i*2-1].y2=y2,line[i*2-1].k=1;
            line[i*2].x=x2,line[i*2].y1=y1,line[i*2].y2=y2,line[i*2].k=-1;
            a[i*2-1]=y1;
            a[i*2]=y2;
        }
        N<<=1;
        sort(line+1,line+N+1);
        sort(a+1,a+N+1);
        for(int i=1;i<=N;++i)
        {
            if(i==1||a[i]!=a[i-1])
                b[++M]=a[i];
        }
        build(1,1,M-1);
        double ans=0;
        for(int i=1;i<N;++i)
        {
            int id1=lower_bound(b+1,b+M+1,line[i].y1)-b;
            int id2=lower_bound(b+1,b+M+1,line[i].y2)-b;
            change(1,id1,id2-1,line[i].k);
            ans+=(line[i+1].x-line[i].x)*t[1].len;
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",now,ans);
    }

    return 0;
}

注意若数据有$N$组，那记录扫描线有$2N$组，则线段树大小至少开到$8N$。注意在$pushup$操作中，我们要注意叶节点的判断，例如在$[1,10]$建线段树，叶节点区间$[7,7]$编号为25，如果不判断叶节点，那他的$pushup$可能会用到50和51号节点，超过了40（超过了$4\ast size$），如果不想判断叶节点则线段树开到80的大小，即开到$16N$（$8\ast size$）。但要注意，如果有多组测试数据，会重复使用覆盖同一个线段树，则想要使用$16N$（$8\ast size$），需要在使用下一组数据前将整个线段树重置。

3.动态开点和线段树合并

在一些计数问题中，线段树用于维护值域（一段权值范围），这样的线段树也称为权值线段树。为了降低空间复杂度，我们可以不建出整棵线段树的结构，而是在最初只建立一个根节点，代表整个区间，当需要访问线段树的某棵子树（某个区间）时，再建立代表这个子区间的节点。采用这种方法维护的线段树称为动态开点的线段树。动态开点的线段树抛弃了完全二叉树父子节点的2倍编号规则，改为使用变量记录左右子节点的编号（相当于指针）。同时，它也不再保存每个节点代表的区间，而是在每次递归访问的过程中作为参数传递。下面是一个动态开点的线段树的节点结构。

struct SegmentTree{
    int lc,rc; //左右子节点的编号
    int dat; //区间最大值
}tr[SIZE*2];

int build() //新建一个节点
{
    tot++;
    tr[tot].lc=tr[tot].rc=tr[tot].dat=0;
    return tot;
}

//在main函数中
tot=0;
root=build(); //根节点

下面的代码对线段树单点修改的过程稍加变动，实现了在动态开点的线段树中把$val$位置上值加$delta$，同时维护区间最大值的操作。

void insert(int p,int l,int r,int val,int delta)
{
    if(l==r)
    {
        tr[p].dat+=delta;
        return;
	}
    int mid=(l+r)>>1;
    if(val<=mid)
    {
        if(!tr[p].lc)
            tr[p].lc=build(); //动态开点
        insert(tr[p].lc,l,mid,val,delta);
    }
    else
    {
        if(!tr[p].rc)
            tr[p].rc=build(); //动态开点
        insert(tr[p].rc,mid+1,r,val,delta);
    }
    tr[p].dat=max(tr[tr[p].lc].dat,tr[tr[p].rc].dat);
}
insert(root,1,n,val,delta); //调用

常规线段树的其他操作也可以通过类似的变动，在动态开点的线段树上实现，这里就不在赘述。一棵维护值域$[1,n]$的动态开点的线段树在经历$m$次单点操作后，节点数量的规模为$O(mlogn)$，最终至多有$2n-1$个节点。

如果有若干颗线段树，它们都维护相同的值域$[1,n]$，那么它们对各个子区间的规划显然是一致的。假如有$m$次单点修改操作，每次操作在某一棵线段树上执行。所有操作完成后，我们希望把这些线段树对应位置上的值相加，同时维护区间的最大值。

该问题可以通过线段树合并算法实现。我们依次合并这些线段树。合并两颗线段树时，用两个指针$p,q$从两个根节点出发，以递归的方式同步遍历两颗线段树。换句话说，$p,q$指向的节点总是代表相同的子区间。

1.若$p,q$之一为空，则以非空的那个作为合并后的节点。

2.若$p,q$均不为空，则递归合并两颗左子树和两颗右子树，然后删除节点$q$，以$p$为合并后的节点，自底向上更新最值信息。若已到达叶子节点，则直接把两个最值相加即可。

int merge(int p,int q,int l,int r)
{
    if(!p) return q;
    if(!q) return p;
    if(l==r)
    {
        tr[p].dat+=tr[q].dat;
        return p;
	}
    int mid=(l+r)>>1;
    tr[p].lc=merge(tr[p].lc,tr[q].lc,l,mid);
    tr[p].rc=merge(tr[p].rc,tr[q].rc,mid+1,r);
    tr[p].dat=max(tr[tr[p].lc].dat,tr[tr[p].rc].dat);
    return p; //以p作为合并后的节点，相当于删除q
}

仔细观察可以发现，若线段树合并过程中发生递归，则必定会导致$p,q$之一被删除。因此，在完成所有线段树的合并后，$merge$函数被执行的次数不会超过所有线段树的节点总数加一。故这个合并过程的时间复杂度为$O(mlogn)$，与完成所有单点修改操作的时间复杂度相等，是一个很高效的过程。

我们会在0x63节结合具体例题，探讨线段树合并的应用并完成代码实现。