讲义：线段树 » 老官童鞋gogo的博客

学习线段树，你需要先完成树、数组、分治思想、递归的学习（可以说是学习成本极低了）

引入

线段树是一个用途极为广泛的数据结构，在提高组及以上的比赛中经常看到它的身影。

现在我有一个问题，给一个长度为 $n$ 的序列，我需要将序列中一个范围内的每一个数进行一次运算，例如加上 $x$ ，也就是区间修改，然后查询修改后一个区间范围内所有值的和或者其他量，也就是区间查询，连续进行几次操作，输出每次区间查询的结果。

现在给你们五分钟的时间，你们就能写出来。主要代码大概就是这个样子：

#include<iostream>
#include<cstdio>
using namespace std;
int a[10010],n,t,opt;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&opt);
        if(opt==1){
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            for(int i=x;i<=y;i++)
                a[i]+=k;
        }
        else{
            int x,y,sum=0;
            scanf("%d%d",&x,&y);
            for(int i=x;i<=y;i++)
                sum+=a[i];
            printf("%d\n",sum);
        }
    }
    system("pause");
    return 0;
}

这个问题对于很多初学者来说都不是困难的事情，几个 for 循环就能解决的问题，为什么还要讲一个线段树，~~直接下课吧~~。但是，你把这套代码交到洛谷线段树模板这道题上，收获的是满满的TLE。

事情远没有那么简单，在大部分情况下，我们除了需要保证结果的准确，还需要追求速度的提升。那么一些学识广的同学又会说：树状数组处理这种问题不也是很快的吗？的确，线段树与树状数组在同一个复杂量级上（都可以在 $O(\log n)$ 的时间内完成一次操作），树状数组的常数甚至优于线段树，但是树状数组能够完成的操作，线段树也能完成，但是线段树能完成的操作，树状数组不一定能完成。

故，无论如何，学习线段树是非常必要的。

定义

前面说了这么多，也没有介绍线段树的定义。

线段树（segment tree）是一种基于分治思想的二叉树，它的每一个节点都对应了一个 $[L,R]$ 区间，叶子节点对应的区间 $L=R$ 。每一个非叶子节点 $[L,R]$ 其左子节点的区间都为 $[L,\frac{(L+R)}{2}]$ ，右子节点的区间都为 $[\frac{(L+R)}{2},R]$ 。这里例子不举多了，一个能够存储 $10$ 个节点的线段树如下图所示。

线段树

因为线段树对区间进行二分，是一颗平衡二叉树（平衡二叉树是什么不重要，想要深入了解的话可以看我的博客文章：平衡二叉树），所以树高为 $O(\log n)$ ，树上操作的时间复杂度和树高相关。线段树主要用于更新和查询，一般至少有一个是区间更新或者查询。更新和查询类型的变化多样，灵活运用线段树可以解决多种问题。

限于时间问题，这里只讲解线段树的基本操作，区间查询、单点修改和区间查询、区间修改中求最值以及加和乘两种运算（其余运算类比即可）。

原理：线段树的基本操作

线段树的存储方式

为了更加方便的讲解存储方式，这里以区间最值查询问题来举例。

对于区间最值（最大值或者最小值）查询问题，线段树的每个节点都包含三个变量： $l,r,mx$ ，其中 $l$ 和 $r$ 分别表示区间的左右端点， $mx$ 表示 $[l,r]$ 区间的最值。这里以最大值为例（最小值同），按照定义上面的图，给出 $10$ 个元素a[11]={0,5,3,7,2,12,1,6,5,4,8,15}，构建的线段树如下图所示：

线段树

每一个点的圈内的有序数对表示 $l,r$ ，圈外数字表示该节点表示区间内的最大值，最底层的节点从左到右分别表示a[1]$\sim$ a[10]。

线段树除了最后一层，其他层构成了一颗满二叉树，因此采用顺序存储方式，用一个结构体数组tree[]存储节点。若一个节点的存储下标为 $k$ ，则其左子节点的下标为 $2k$ ，其右子节点的下标为 $2k+1$ 。那么一个节点所存储的三个变量就可以使用tree[k].l、tree[k].r、tree[k].mx表示。、

struct Node
{
    long long l,r,mx;
}tree[1000001];

线段树根节点的存储下标（ $k$ ）为 $1$ ，左右子节点根据上述规则编号，最后得到一颗线段树，也就是说线段树内所有有意义的节点并不一定是顺序编号的，例如：

线段树

这里圈外的数字表示该节点的下标。

创建线段树

可以采用递归的方法创建一颗线段树，步骤如下：

判断是否为叶子节点，根据上述原理可知，叶子节点所存储的数据就是给的数组$\mathbb{a}$中的元素值，那么如果该点的 $l,r$ 值满足 $l=r$ ，那么这个点的最值就是对应位置的元素值。
如果不是叶子节点，即 $l\neq r$ 则递归创建左子树和右子树。
节点的区间最值等于该节点左右子树的最值的最大值。

void build(int k,int l,int r)//建树：k表示当前节点，l表示当前区间的左端点，r表示当前区间的右端点
{
	if(l==r)//当l==r时，表示建树建到了叶子结点，退出递归
	{
		tree[k].mx=a[l];//a[i]表示原始数据
		return;
	}
	int mid=(l+r)>>1;//位运算，即(l+r)/2
	build(k<<1,l,mid);//建立左子树
	build(k<<1|1,mid+1,r);//建立右子树
	tree[x].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);//更新最值
	return;
}

单点修改

单点修改指修改一个元素的值，例如将 $a_i$ 修改成 $v$ 。采用递归进行点更新，步骤如下：

如果是叶子节点， $l=r=i$ ，则修改该节点的最值为 $v$。
如果是非叶子节点，则判断是在左子树中还是右子树中更新。
返回时更新节点的最值。

例如，修改第五个节点的值为 $14$ 时，先从树根向下找第 $5$ 个元素所在的叶子节点，将其值改为 $14$ ，返回时更新路径上所有节点的最值。

线段树

图中蓝线表示递推过程，红线表示回溯过程及其操作，下同。

void add(int k,int i,int v)//单点修改：k表示当前节点，i表示当前要修改的数据的位置，y表示要修改多少的值
{
	if(tree[k].l==tree[k].r)//找到了叶子结点，即i点，退出递归
	{
		tree[k].mx=v;//这里的=可以换成其他运算符
		return;
	}
	int mid=(tree[k].l+tree[k].r)>>1;
	if(i<=mid)//若要找的点在自己的左儿子表示的区间中
		add(k<<1,tree[k].l,mid,i,v);
	if(i>mid)//若要找的点在自己的右儿子表示的区间中
		add(k<<1|1,mid+1,tree[k].r,i,v);
	tree[k].mx=max(tree[k<<1].mx,tree[k<<1|1].mx);//更新节点
}

区间查询

区间查询指查询一个 $[l,r]$ 区间的最值。采用递归的方法进行区间查询，步骤如下：

若节点所在的区间被查询区间 $[l,r]$ 覆盖，则返回该节点的最值。
判断是在左子树中查询还是在右子树中查询。
返回最最值。

例如，在原图中查询 $[3,5]$ 的最值，过程如图：

线段树

int ask(int k,int l,int r)//单点查询：k表示当前节点l表示要查询的区间的左端点，r表示要查询的区间的右端点。
{
	if(l<=tree[k].l&&tree[k].r<=r)//如果当前区间完全包括在要查询的区间的范围内，返回节点的值
		return tree[k].mx;
	int mid=(tree[k].l+tree[k].r)>>1;
	int res=0;
	if(l<=mid)//查询左儿子
		res=max(ask(k<<1,l,r),res);
	if(r>mid)//查询右儿子
		res=max(ask(k<<1|1,l,r),res);
	return res;//返回最值
}

段落小结

至此，你已经学会了构建线段树、单点修改、区间查询的操作，虽然是以最大值为例讲解，但是将其更换为其他运算操作依旧成立。

但是线段树更加强大之处在于它可以实现区间修改和区间查询。但是连续使用单点修改的方法进行区间修改的时间复杂度较高，所以我们需要一个懒惰标记，下面讲解懒惰标记的使用

原理：懒惰标记与区间操作

懒惰标记

懒惰标记是什么？本区间已经被更新过了，但是子区间却没有被更新过，懒惰标记记录下来被更新的信息是什么。

你可能还是不懂，但是在后面的实例讲解中，你会有更加深刻地理解。

区间更新

对 $[l,r]$ 区间进行更新，例如将 $[l,r]$ 区间的所有元素都更新成 $v$ ，步骤如下：

若当前节点的区间被 $[l,r]$ 完全覆盖，则仅对该节点进行更新并做好懒惰标记，表示该节点已经被更新，对该节点的子节点暂时不更新，我们可以在查询的时候根据懒惰标记再向下更新（减少了一些不必要的操作，大幅减小复杂度）。
判断是在左子树中更新还是在右子树中更新。在更新过程中，可能会碰到带有懒惰标记的节点，那么就将该点的懒惰标记传给子节点，并清除当前节点的懒惰标记。
在返回时更新最值。

例如，在 $[1,10]$ 区间的线段树中修改 $[4,8]$ 区间的值为 $20$ ，过程如下：

线段树

void pushdown(long long k)//懒惰标记下推：k表示懒惰标记所在节点
{
    if(tree[k].lz!=0)//判断是否有懒惰标记
    {
        tree[k<<1].lz=tree[k].lz;//将懒惰标记传递给左右儿子
        tree[k<<1|1].lz=tree[k].lz;
        long long mid=(tree[k].l+tree[k].r)>>1;
        tree[k<<1].mx=tree[k].lz;//修改当前节点的值
        tree[k<<1|1].mx=tree[k].lz;
        tree[k].lz=0;//清空标记
    }
    return;
}
void update(long long k,long long l,long long r,long long v)//区间修改，k表示当前修改的节点编号，l表示要修改的区间左端点，r表示要修改的区间右端点，v表示将[l,r]区间内的值改为v
{
    if(tree[k].l>=l&&tree[k].r<=r)
    {
        tree[k].mx=v;//将要修改的值乘区间元素个数于原数相加得到当前值
        tree[k].lz=v;//标记懒惰标记
        return;
    }
    pushdown(k);//懒惰标记下移
    long long mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid)
        update(k<<1,l,r,v);
    if(r>mid)
        update(k<<1|1,l,r,v);
    tree[k].mx=(tree[k<<1].mx,tree[k<<1|1].mx);
    return;
}

这时候懒惰标记还没有发挥作用，不要急，看一下区间查询。

区间查询

带懒惰标记的区间查询和普通的区间查询有所不同，在查询中如果遇到节点有懒惰标记的节点就下传懒惰标记，相当于在查询的时候顺便更新了节点。

以上图为例，查询 $[6,7]$ 区间的最值，过程如下：

线段树

深蓝色表示查询操作的递推及其操作，深红色表示回溯结果。

long long search(long long k,long long l,long long r)//区间查询
{
    if(tree[k].l>=l&&tree[k].r<=r)
        return tree[k].mx;
    pushdown(k);//查询是将懒惰标记下移
    long long s=0;
    long long mid=(tree[k].l+tree[k].r)>>1;
    if(l<=mid)
        s=max(s,search(k<<1,l,r));
    if(r>mid)
        s=max(s,search(k<<1|1,l,r));
    return s;
}