线段树

Deakin · 2026-03-31 23:43:01 · 算法·理论

序

线段树是基于分治思想的二叉树，用于动态且高效地维护区间信息。每个节点对应一个区间，叶子节点对应单个元素，父节点存储子节点信息的合并。

相较于其他简单数据结构，线段树的优势是能在 O(\log{n}) 级的时间内进行区间的修改和查询。

前置芝士：二叉树、递归分治。

一、基础线段树

P1531 I Hate It：

比如有 n 个学生的成绩，m 次操作，你要查询某些区间内的最大值，还要支持单个学生成绩修改。

当 n,m \le 10^5、动态修改查询时就需要用到更高级的数据结构了——线段树。

1. 维护简单的“和/最值”

如果我们知道 [25,50],[51,100] 的最大值，[25,100] 的最大值也能很快算出。

你很快想到，将区间不断二分，分别维护子区间最值并向上合并。单点修改递归至叶子节点，回溯时逐层更新信息，单次查询、修改复杂度均为 O(\log{n})，效率优秀。

具体实现

用堆式储存，根节点编号为 1，节点 u 的左右儿子分别是 2u、2u+1，数组大小 4n。

Q：为什么数组要开 4n？
实际使用中，开 4n 是经验值，最坏情况（n 不是 2 的幂）下刚好够用，避免越界。

有 n 个叶子节点的平衡二叉树高度为 h=\lceil\log{n}\rceil+1。
按满二叉树来算，节点总数最多 2^h-1，代入算得最大节点数 \le 4n-1。

然后确定好要维护的信息，这里用最大值来说明：

• 合并：取左右的最大值。在修改或建树后，通过合并函数向上更新。
• 单点修改：一直递归到叶子节点，修改叶子节点的值，在回溯时合并。
• 查找：和合并差不多，只是要合并的是多个被查询区间完全覆盖的节点（不妨称它们为本次查询中的“类叶子节点”）。仅递归部分覆盖的区间，对完全覆盖的区间直接合并信息返回答案。

一定要自己画图模拟理解一下。

参数： 递归时用 u,l,r 来表示当前递归到节点 u 管的区间 [l,r]。[x,y] 表示目标区间（单点修改只有 x），k 表示更新操作参数。
函数外调用时一开始的 u,l,r 用 1,1,n 表示根节点，比如 qry(1,1,n,x,y) 返回 [x,y] 中的最大值。

向上合并信息：

void up(int u){
    //取左右子树的最大值的最大值
    t[u]=max(t[u<<1],t[u<<1|1]);
}

建树：遍历所有节点和更新信息，线性复杂度。

//把数组[l,r]这一段建成一棵子树，根为u
void build(int u,int l,int r){
    if(l==r){t[u]=a[l];return;}//叶子节点
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    up(u);//合并子节点信息
}

单点更新：递归到叶子节点，只走一条树链，易证复杂度为 O(\log{n})。

//把数组下标为x的值改为k
void chg(int u,int l,int r,int x,int k){
    //到叶子节点直接更新
    if(l==r){t[u]=k;return;}
    int mid=(l+r)>>1;
    //根据x判断往左往右递归
    if(x<=mid)chg(u<<1,l,mid,x,k);
    else chg(u<<1|1,mid+1,r,x,k);
    up(u);//合并
}

区间最大值查询：只有部分被覆盖才继续递归。

//查询数组[l,r]内的最大值
int qry(int u,int l,int r,int x,int y){
    if(x<=l && r<=y)return t[u];//被完全覆盖，直接返回之前算好的最大值，不用继续递归
    int mid=(l+r)>>1,as=-inf;//极小值
    if(x<=mid)as=max(as,qry(u<<1,l,mid,x,y));
    if(y>mid)as=max(as,qry(u<<1|1,mid+1,r,x,y));
    return as;
}

感谢 @Seauy 指出错误，现给出区间操作复杂度证明，分三种情况：

1. 完全被覆盖：直接返回，不递归。
2. 一端被覆盖，另一端没被覆盖（左右边被覆盖等价，故按左边被覆盖来证明）：
   要么递归左儿子和右儿子（此时左儿子为情况一，右儿子仍是情况二）。
   要么只递归左儿子，仍是情况二，于是最坏是访问左儿子递归右儿子，每层最多访问了 2 个节点。
3. 查询区间完全在内部（不到左右两端）： 要么同时递归左儿子和右儿子（此时左右儿子都是前两个情况，总每层最坏 4 个节点）。
   要么只递归其中一边，这时儿子节点三种情况都有可能，子节点最坏仍是情况三，最多每层访问 4 个节点。

最多每层访问 4 个节点，树高为 O(\log{n})，总共最多访问 4\cdot\log{n} 个节点，故单次时间复杂度 O(\log{n})！再次感谢 @Seauy（此前错误地认为动态开点只需要 2m\cdot\log{n} 的空间）。

上面的代码中，只展示了区间最大值，其实完全可以改成求和、按位与、或和异或等。

习题： codeforces-339D， P2068 统计和， P1198 [JSOI2008] 最大数， P4588 [TJOI2018] 数学计算， P2184 贪婪大陆， P4145 上帝造题的七分钟 2 / 花神游历各国， P3792 由乃与大母神原型和偶像崇拜。

后三题对于刚接触线段树的读者有一定难度，需要额外技巧（容斥原理、线段树势能分析和一定数论基础），建议先往下阅读，以免影响兴趣。

二、区间更新与懒标记

上述写法仅能支持的单点修改，面对区间修改就一个个更新，太讷了。

P3372 【模板】线段树 1：

比如一个长度为 n 的数列，要支持随时查询区间和、区间所有数加 k。

1. 懒标记引入

我们想要快速更新一个区间，但又不想要真的单独更新每一个叶子节点，因为那样时间复杂度就到了 O(n)。

Q：区间查询只会访问 O(\log{n}) 级数的节点的关键在于合并的是多个“类叶子节点”，如果只修改到被修改区间完全覆盖的“类叶子节点”，就不往下递归了。时间复杂度同样是优秀的 O(\log{n})，但之后要查询下面未更新的信息该怎么处理呢？

你想到，每次更新完“类叶子节点”再在当前节点上记一笔账，表示这段区间的子节点还欠着没有更新，等到之后访问的时候一起更新。
这个记账的东西，就叫懒标记。人如其名，它真的很懒，不到万不得已绝不干活，干活就是把帐分给儿子还。

有记账就有还账，因为懒，还账自然不是一次性全还完，还账的时机就在需要往下走的时候——无论是更新还是查询，只要递归进入左右子节点前，都要先把这笔帐往下发，传到新操作的“类叶子节点”。

具体实现

因为要多维护一个懒标记，所以数组要进行调整，可以用 struct 封装信息。

struct node{
    ll s,ta;//s:和, ta:add懒标记
}t[4*maxn];

接下来着重讲解区间更新和标记下传，其他函数记得要在递归进入左右子节点前都 down 一次，build 时要清空标记。

下传标记：

void pushta(int u,int l,int r,ll k){//更新子节点并记账
    t[u].s+=1ll*(r-l+1)*k;//更新当前节点，使当前节点信息正确，不影响up
    t[u].ta+=k;//做一个标记，表示子节点待更新！
}
void down(int u,int l,int r){
    //把帐往下发，给子节点记账
    int mid=(l+r)>>1;
    pushta(u<<1,l,mid,t[u].ta);
    pushta(u<<1|1,mid+1,r,t[u].ta);
    t[u].ta=0;//标记的任务完成，记得清空！
}

区间加：

void chg(int u,int l,int r,int x,int y,ll k){
    if(x<=l && r<=y){pushta(u,l,r,k);return;}//更新“类叶子节点”并记上一笔账，可以直接调用pushta
    down(u,l,r);//记得递归前下传标记！
    int mid=(l+r)>>1;
    if(x<=mid)chg(u<<1,l,mid,x,y,k);
    if(y>mid)chg(u<<1|1,mid+1,r,x,y,k);
    up(u);
}

习题： P2357 守墓人， P3870 [TJOI2009] 开关 （经验包：P2574 XOR的艺术，P2846 [USACO08NOV] Light Switching G，P5057 [CQOI2006] 简单题）， P1558 色板游戏， P1438 无聊的数列， P1471 方差（经验包：P5142 区间方差，P2122 还教室）。

后三题略难（需结合位运算、差分、初中数学知识）。

2. 多标记互斥

P1253 扶苏的问题：

现在问题更复杂了，不仅有区间加、查询最大值，还有区间赋值。

这样我们不能只维护一个标记了，显然不够用。

struct node{
    bool f;//f:是否有赋值
    int x,ta,se;//x:最大值, ta:加法标记, se:赋值
}t[4*maxn];

用了多个标记就有有问题了，一个节点上可能有多个待办事项，要先做什么？还可能出现冲突，该怎么办？

赋值操作会导致之前所有标记失效，尚未下传的标记都不再有意义，在更新时要把加法标记清空。赋值之后的加法操作相当于给赋值操作加法，这样就避免了两个标记同时存在。既然没有两个标记同时存在，下传顺序就无所谓了。

具体实现

下传标记：

void pushse(int u,int k){
    t[u].x=k;
    t[u].se=k;
    t[u].f=1;
    t[u].ta=0;//清空加法标记
}

void pushta(int u,int k){//不用l,r
    t[u].x+=k;
    if(t[u].f)t[u].se+=k;
    else t[u].ta+=k;
}

void down(int u){
    //顺序无所谓
    pushta(u<<1,t[u].ta);
    pushta(u<<1|1,t[u].ta);
    t[u].ta=0;
    if(t[u].f){
        pushse(u<<1,t[u].se);
        pushse(u<<1|1,t[u].se);
        t[u].f=0;//f必须清
        t[u].se=0;//se清不清都无所谓
    }
}

习题： P4560 [IOI 2014] Wall 砖墙。

3. 多标记共存与优先级

P3373 【模板】线段树 2：

维护支持随时区间加、乘、查询和的数列。

Q：那么遇到了标记可能同时存在的情况呢？比如区间加和区间乘。

你注意到，一个区间先加后乘和先乘后加的结果是不一样的。假设某节点原值为 a。

• 先加 k 再乘 v 得到 (a+k)v=av+kv。
• 先乘 v 再加 k 得到 av+k。

都可以统一表示成 av+k 的形式，下传顺序就确定了——先乘后加，就能保证子节点的标记能被正确合并，乘法标记优先级更高。

通过分析不同标记之间的影响确定下传顺序，在其他复杂的标记上同样适用。

具体实现

下传标记：

void down(int u,int l,int r){
    pushtm(u<<1,t[u].tm);
    pushtm(u<<1|1,t[u].tm);
    t[u].tm=1;
    int mid=(l+r)>>1;
    pushta(u<<1,l,mid,t[u].ta);
    pushta(u<<1|1,mid+1,r,t[u].ta);
    t[u].ta=0;
}

习题： P5579 [PA 2015] Siano。

三、复杂的信息合并

维护需要左右儿子互相“拼凑”的信息。

这一章我们会讲复杂信息合并，以“P4513 小白逛公园”为例。 你会发现，即使没有懒标记，信息本身也可能很复杂——比如最大子段和需要维护 4 个值。 但好消息是，框架完全一样，只是 up 和 qry 的合并逻辑变得更丰富。

1. 为什么需要复杂信息

单靠左右儿子的最大子段和无法算出父节点的最大子段和。
Q：要算出父节点最大子段和，你至少需要维护几个信息？

你很快发现，区间最大子段和有三种情况：

• 完全在左儿子
• 完全在右儿子
• 跨越左右儿子

一和二很好办，取左右儿子区间最大子段和的最大值。
第三种情况只能由左右儿子“拼凑”出来，而“拼凑”所需的信息，正是左儿子的最大后缀和和右儿子的最大前缀和。

这样我们就解决了父节点的最大子段和。
但试想一下，给你左右儿子的这三个信息，你能算出父节点的最大前后缀和吗？

你很快发现，最大前缀和有两种情况：

• 左儿子最大前缀和
• 左儿子的和加上右儿子最大前缀和

后缀和同样需要右儿子的和，所以还要多维护一个区间和。 这样我们就解决了父节点的最大前后缀和，至于区间和，它不依赖于其他信息，可以独立算。

把这些信息封装起来：

struct node{
    int p,s,m,a;//p:前缀, s:后缀, m:中缀, a:和
}t[4*maxn];

2. 标记之间的依赖关系

我们发现线段树维护某些信息可能依赖其他信息，比如最大子段和依赖最大前后缀和，最大前后缀和依赖区间和。也可能可以独立更新，比如区间和。

具体实现

合并：

void up(int u){
    int lv=u<<1,rv=u<<1|1;
    t[u].p=max(t[lv].p,t[lv].a+t[rv].p);
    t[u].s=max(t[rv].s,t[rv].a+t[lv].s);
    t[u].m=max(max(t[lv].m,t[rv].m),t[lv].s+t[rv].p);
    t[u].a=t[lv].a+t[rv].a;
}

习题： P6492 [COCI 2010/2011 #6] STEP （经验包：P2572 [SCOI2010] 序列操作）， P2894 [USACO08FEB] Hotel G。

3. 特别的合并

P4198 楼房重建：

一排楼房，从左到右 1 \sim n 号。小 A 在 (0,0) 往右看。第 i 个楼房能被看到，仅当小 A 到 (i,H_i) 的视线不被前 i-1 个楼房阻挡（楼顶刚好与视线相交也算阻挡）。

施工队建造了 M 天。初始时，所有楼房高度均为 0。在第 i 天，建筑队将会将第 X_i 座房屋的高度变为 Y_i。请你帮小 A 数数每天在建筑队完工之后，他能看到多少栋楼房？

我画了一些图，其中每条虚线两格高。

定义斜率为 \Large\frac{H_i}{i}。
观察得出，只有楼房的斜率严格大于其左边所有楼房的斜率时才能被看到。所以除了从 (0,0) 能看到的楼房数（不受左边楼房的限制），还需要维护最大斜率。这样才能在合并时正确处理右子树的贡献。

struct node{
    int s;//s:(0,0)能看到当前区间的楼数(不计区间之外的楼)
    double x;//x:楼的最大斜率
}t[4*maxn];

知道左右区间的最大斜率和在“无限制”情况下能看到的楼房数，要如何求出父节点的这些信息？
最大斜率简单，难的是“无限制”下能看到的楼房数。

你发现了这题的关键：

• 左区间能看到的，总区间一样能看到。
• 右区间能看到的，只有斜率严格大于左区间最大值的。

新的问题来了，我们只知道右区间在“无限制”下能看到的楼房数，却并不知道在“严格大于左区间最大值的限制”下还剩多少能看到。
而且这个信息也绝非多维护两三条其他信息所能维护的。

这时候我们需要快速查询某个区间在斜率严格大于 k 的限制下所能看到的楼房数。

动态且高效的区间查询？听着怎么那么像线段树能做的事啊。

维护最大值 x，次大值 sx，最大值个数 c，每个节点有三种情况：

我第一次接触吉如一线段树是在 26/2/13 左右（至于为什么记这么清楚，问就是样例都没过调到凌晨三点），经过两天学习痛苦的调代码终于过了P10639 BZOJ4695 最假女选手。

总之，吉如一线段树的调试难度较高，建议先理解原理再动手实现。

2.区间历史最大值

只有区间加会改变历史最大值，但加法标记只有在最大时下传才能正确更新历史最大值。

现在如果只考虑修改，不考虑下传，每次加法操作都是在节点上操作序列的末尾添加一个 k。历史最大值就是原来的最大值加上整个操作序列最大的前缀和。

再来考虑下传标记，我们每次下传懒标记相当于把整个操作序列加入到儿子操作序列的末尾，对于一个线段树上的区间，实际上操作序列对历史最大值的贡献即区间最大值加上操作序列最大的前缀和。

因此需要维护操作序列的和 ta，操作序列最大的前缀和 ha。又因为最大值和非最大值的更新不同，所以实际要维护最大值当前加法标记 t1，非最大值当前加法标记 t2，最大值历史最大加法标记 h1，非最大值历史最大加法标记 h2。

• 更新时先更新历史值：子节点的 h1/h2 与子节点的 t1/t2 分别加父节点传下来的 h1/h2 的和取较大的。子节点的历史最大值 b 与子节点的 x 加父节点传下来的 h1 的和取较大的。
• 在更新当前值：子节点的 x/t1 加父节点传下来的 t1，sx/t2 加父节点传下来的 t2。注意没有次大值的就不要加，保持 -inf。

这个顺序是必须的，因为 t[u].x+h1 要用到更新前的 t[u].x。如果先更新当前值，历史最大值就会错误地变大。

或许按理来说我应该写到复杂的标记下传，思考ing。但我觉得历史最值还是挺难的，放在第三章会把人劝退的。

历史最值的标记下传逻辑较复杂，再配合上区间取 min 和区间加，需要仔细区分最大值和非最大值的标记。因为一些细节理解不到位（比如 down 的时候是取儿子最大的最大值判断下传针对最大值还是针对次大值的标记，不是用当前节点最大值）或手误犯了简单错误调个三五天都是没问题的。

具体实现

struct node{
    long long s;//s:和,
    int x,b,sx,c;//x:最大,b:历史最大,sx:严次大,c:最大个数
    //1针对最大值,2针对非最大值
    int t1,t2,h1,h2;//t_:当前标记,h_:历史标记最大值
}t[4*maxn];

void up(int u){
    int lv=u<<1,rv=u<<1|1;
    t[u].s=t[lv].s+t[rv].s;     //s
    t[u].x=max(t[lv].x,t[rv].x);//x
    t[u].b=max(t[lv].b,t[rv].b);//x
    if(t[lv].x==t[rv].x){       //sx,c
        t[u].sx=max(t[lv].sx,t[rv].sx);
        t[u].c=t[lv].c+t[rv].c;
    }else if(t[lv].x>t[rv].x){
        t[u].sx=max(t[lv].sx,t[rv].x);
        t[u].c=t[lv].c;
    }else if(t[lv].x<t[rv].x){
        t[u].sx=max(t[lv].x,t[rv].sx);
        t[u].c=t[rv].c;
    }
    t[u].t1=t[u].t2=t[u].h1=t[u].h2=0;//初始化标记
}

void build(int u,int l,int r){
    if(l==r){
        t[u].s=t[u].b=t[u].x=a[l];//s,b,x=a
        t[u].sx=-inf;t[u].c=1;//单节点没有次大值，最大值一个
        t[u].t1=t[u].t2=t[u].h1=t[u].h2=0;//初始化标记
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    up(u);
}

void push(int u,int l,int r,int t1,int t2,int h1,int h2){
    t[u].s+=1ll*t[u].c*t1+1ll*(r-l+1-t[u].c)*t2;//最大值贡献+非最大值贡献
    //1.先更新历史值
    t[u].b=max(t[u].b,t[u].x+h1);//更新历史最大值
    t[u].h1=max(t[u].h1,t[u].t1+h1);//针对最大值历史最大标记
    t[u].h2=max(t[u].h2,t[u].t2+h2);//针对次大值历史最大标记
    //2.更新当前值/标记
    t[u].x+=t1;//最大值
    if(t[u].sx!=-inf)t[u].sx+=t2;//次大值
    t[u].t1+=t1;t[u].t2+=t2;
}
void down(int u,int l,int r){
    int mid=(l+r)>>1,lv=u<<1,rv=u<<1|1;
    int t1=t[u].t1,t2=t[u].t2,
        h1=t[u].h1,h2=t[u].h2,
        mx=max(t[lv].x,t[rv].x);
    if(mx==t[lv].x)push(lv,l,mid,t1,t2,h1,h2);
    else push(lv,l,mid,t2,t2,h2,h2);
    if(mx==t[rv].x)push(rv,mid+1,r,t1,t2,h1,h2);
    else push(rv,mid+1,r,t2,t2,h2,h2);
    t[u].t1=t[u].t2=t[u].h1=t[u].h2=0;
}

void chgadd(int u,int l,int r,int x,int y,int k){
    if(x<=l && r<=y){push(u,l,r,k,k,k,k);return;}
    down(u,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)chgadd(u<<1,l,mid,x,y,k);
    if(y>mid)chgadd(u<<1|1,mid+1,r,x,y,k);
    up(u);
}
void chgmn(int u,int l,int r,int x,int y,int v){
    if(v>=t[u].x)return;//无效的更新,还会破坏标记的正确性
    if(x<=l && r<=y && t[u].sx<v){//v刚好位于sx和x中间才更新
        int k=t[u].x-v;
        push(u,l,r,-k,0,-k,0);//针对最大值的减法
        return;
    }
    down(u,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)chgmn(u<<1,l,mid,x,y,v);
    if(y>mid)chgmn(u<<1|1,mid+1,r,x,y,v);
    up(u);
}

习题： P10639 BZOJ4695 最假女选手， P4314 CPU 监控。

现在你可以写P4198 楼房重建的 O(n+m \log{m}) 做法了。反正我是不想再调代码了，为了我的身心健康着想。