当前位置：首页 > news >正文

初识线段树

news 2025/8/20 10:24:46

用简单的言语解开超载的心
有些情绪是该说给懂的人听
你的热泪比我激动怜惜
我发誓要更努力更有勇气

初识线段树

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O(log⁡N)O(\log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询 (区间求和，求区间最大值，求区间最小值)等操作。

线段树的基本结构与建树

线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

有个大小为 5 的数组 $a=\{10,11,12,13,14\}$ ,要将其转化为线段树，有以下做法：设线段树的根节点编号为 1, 用数组 $e$ 来保存我们的线段树， $e_i$ 用来保存线段树上编号为 $i$ 的节点的值 (这里每个节点所维护的值就是这个节点所表示的区间总和)。

我们先给出这棵线段树的形态，虽说是树，但是可以用矩阵来简化表示一下其中的关系，如图所示：
请添加图片描述

图中每个节点都标明了编号和区间，表示该节点管辖的 $a$ 数组上的位置区间。如 $e_{1}$ 所管辖的区间就是[1,9] ( $a1,a2,⋯,a9a_1,a_2,\cdots,a_9$ ),即 $e_1$ 所保存的值是 $a1+a2+⋯+a9a_1+a_2+\cdots+a_{9}$ 。

通过观察不难发现， $e_i$ 的左儿子节点就是 $e2×ie_{2\times i}$ ， $e_i$ 的右儿子节点就是 $e2×i+1e_{2\times i+1}$ 。如果 $e_i$ 表示的是区间 $[l, r]$ (即 $di=al+al+1+⋯+ard_i=a_l+a_{l+1}+\cdots+a_r$ )的话，那么 $e_i$ 的左儿子节点表示的是区间 $[l,l+r2][l,\frac{l+r}2]$ ， $e_i$ 的右儿子表示的是区间 $[l+r2+1,r][\frac{l+r}2+1,r]$ 。

在实现时，我们考虑递归建树。设当前的根节点为 $u$ ,如果根节点管辖的区间长度已经是 1,则可以直接根据 $a$ 数组上相应位置的值初始化该节点。否则我们将该区间从中点处分割为两个子区间，分别进入左右子节点递归建树，最后合并两个子节点的信息。

在创建树的数组时，需要开到 $4 N$ 的大小！这里不做推导可以自行搜索证明；

这里方便表示，可以提前宏定义lc与rc为u<<1和u<<1|1；

void iuui(int u,int l,int r){e[u]={l,r,a[l]};if(l==r) return ;int mid=l+r>>1;iuui(lc,l,mid);iuui(rc,mid+1,r);e[u].s=e[lc].s+e[rc].s;
}

线段树的区间修改与懒标记

如果要求修改区间 $[l, r]$ ,把所有包含在区间 $[l, r]$ 中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做「懒标记」的东西。

懒标记，简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。

每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。

仍然以最开始的图为例，我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个 $ff_i$ ,表示该节点带的标记值。

只有在查询或者需要访问子节点的时候才进行更新ggxb()操作；更新后清空当前节点的懒标记，将懒标记传到下一层子节点当中；

再对区间修改时，如果当前访问的区间被包含，可直接利用乘法进行更新；

void ggxb(int u){if(!e[u].ff) return ;e[lc].s+=e[u].ff*(e[lc].r-e[lc].l+1);e[lc].ff+=e[u].ff;e[rc].s+=e[u].ff*(e[rc].r-e[rc].l+1);e[rc].ff+=e[u].ff;e[u].ff=0;
}void quxq(int u,int x,int y,int k){if(x<=e[u].l&&e[u].r<=y){e[u].s+=(e[u].r-e[u].l+1)*k;e[u].ff+=k;return ;}int mid=e[u].l+e[u].r>>1;ggxb(u);if(x<=mid) quxq(lc,x,y,k);if(y>mid) quxq(rc,x,y,k);e[u].s=e[lc].s+e[rc].s;
}

线段树的区间查询

区间查询，比如求区间 $[l, r]$ 的总和 (即 $al+al+1+⋯+ara_l+a_{l+1}+\cdots+a_r$ )、求区间最大值/最小值等操作。

仍然以最开始的图为例，如果要查询区间[1,5]的和，那直接获取 $e_{1}$ 的值 (60)即可。

如果要查询的区间为[3,5],此时就不能直接获取区间的值，但是[3,5]可以拆成[3,3]和[4,5],可以通过合并这两个区间的答案来求得这个区间的答案。

一般地，如果要查询的区间是 $[l, r]$ ,则可以将其拆成最多为 $O(log⁡n)O(\log n)$ 个极大的区间，合并这些区间即可求出 $[l, r]$ 的答案。

int iaxy(int u,int x,int y){if(x<=e[u].l&&e[u].r<=y)return e[u].s;ggxb(u);int mid=e[u].l+e[u].r>>1;int s=0;if(x<=mid) s+=iaxy(lc,x,y);if(y>mid) s+=iaxy(rc,x,y);return s;
}

区修+区查

P3372 【模板】线段树 1 - 洛谷

将上面的步骤拼合起来，即可得到整体的模板；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
#define lb(x) ((x)&(-x))
#define lc u<<1
#define rc u<<1|1
const int inf=0x3f3f3f3f;
const int N=1e5+5;
struct edge{int l,r,s;int ff;
}e[4*N];
int n,a[N]; void iuui(int u,int l,int r){e[u]={l,r,a[l]};if(l==r) return ;int mid=l+r>>1;iuui(lc,l,mid);iuui(rc,mid+1,r);e[u].s=e[lc].s+e[rc].s;
}void ggxb(int u){if(!e[u].ff) return ;e[lc].s+=e[u].ff*(e[lc].r-e[lc].l+1);e[lc].ff+=e[u].ff;e[rc].s+=e[u].ff*(e[rc].r-e[rc].l+1);e[rc].ff+=e[u].ff;e[u].ff=0;
}void quxq(int u,int x,int y,int k){if(x<=e[u].l&&e[u].r<=y){e[u].s+=(e[u].r-e[u].l+1)*k;e[u].ff+=k;return ;}int mid=e[u].l+e[u].r>>1;ggxb(u);if(x<=mid) quxq(lc,x,y,k);if(y>mid) quxq(rc,x,y,k);e[u].s=e[lc].s+e[rc].s;
}int iaxy(int u,int x,int y){if(x<=e[u].l&&e[u].r<=y)return e[u].s;ggxb(u);int mid=e[u].l+e[u].r>>1;int s=0;if(x<=mid) s+=iaxy(lc,x,y);if(y>mid) s+=iaxy(rc,x,y);return s;
}void slove(){int m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];iuui(1,1,n);while(m--){int op;cin>>op;if(op==1){int x,y,k;cin>>x>>y>>k;quxq(1,x,y,k);}else{int x,y;cin>>x>>y;cout<<iaxy(1,x,y)<<endl;}}
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

区修+点查

P3368 【模板】树状数组 2 - 洛谷

对单点的查询可以看做是对区间长度为1的区间进行查询，直接套用即可；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
#define lb(x) ((x)&(-x))
#define lc u<<1
#define rc u<<1|1
const int inf=0x3f3f3f3f;
const int N=5e5+5;
struct edge{int l,r,s;int ff;
}e[4*N];
int n,a[N]; void iuui(int u,int l,int r){e[u]={l,r,a[l]};if(l==r) return ;int mid=l+r>>1;iuui(lc,l,mid);iuui(rc,mid+1,r);e[u].s=e[lc].s+e[rc].s;
}void ggxb(int u){if(!e[u].ff) return ;e[lc].s+=e[u].ff*(e[lc].r-e[lc].l+1);e[lc].ff+=e[u].ff;e[rc].s+=e[u].ff*(e[rc].r-e[rc].l+1);e[rc].ff+=e[u].ff;e[u].ff=0;
}void quxq(int u,int x,int y,int k){if(x<=e[u].l&&e[u].r<=y){e[u].s+=(e[u].r-e[u].l+1)*k;e[u].ff+=k;return ;}int mid=e[u].l+e[u].r>>1;ggxb(u);if(x<=mid) quxq(lc,x,y,k);if(y>mid) quxq(rc,x,y,k);e[u].s=e[lc].s+e[rc].s;
}int iaxy(int u,int x,int y){if(x<=e[u].l&&e[u].r<=y)return e[u].s;ggxb(u);int mid=e[u].l+e[u].r>>1;int s=0;if(x<=mid) s+=iaxy(lc,x,y);if(y>mid) s+=iaxy(rc,x,y);return s;
}void slove(){int m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];iuui(1,1,n);while(m--){int op;cin>>op;if(op==1){int x,y,k;cin>>x>>y>>k;quxq(1,x,y,k);}else{int x;cin>>x;cout<<iaxy(1,x,x)<<endl;}}
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

点修+区查

P3374 【模板】树状数组 1 - 洛谷

同理，对单点的修改可以看做是对区间长度为1的区间进行修改，直接套用即可；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
#define lb(x) ((x)&(-x))
#define lc u<<1
#define rc u<<1|1
const int inf=0x3f3f3f3f;
const int N=5e5+5;
struct edge{int l,r,s;int ff;
}e[4*N];
int n,a[N]; void iuui(int u,int l,int r){e[u]={l,r,a[l],};if(l==r) return ;int mid=l+r>>1;iuui(lc,l,mid);iuui(rc,mid+1,r);e[u].s=e[lc].s+e[rc].s;
}void ggxb(int u){if(!e[u].ff) return ;e[lc].s+=e[u].ff*(e[lc].r-e[lc].l+1);e[lc].ff+=e[u].ff;e[rc].s+=e[u].ff*(e[rc].r-e[rc].l+1);e[rc].ff+=e[u].ff;e[u].ff=0;
}void quxq(int u,int x,int y,int k){if(x<=e[u].l&&e[u].r<=y){e[u].s+=(e[u].r-e[u].l+1)*k;e[u].ff+=k;return ;}int mid=e[u].l+e[u].r>>1;ggxb(u);if(x<=mid) quxq(lc,x,y,k);if(y>mid) quxq(rc,x,y,k);e[u].s=e[lc].s+e[rc].s;
}int iaxy(int u,int x,int y){if(x<=e[u].l&&e[u].r<=y)return e[u].s;ggxb(u);int mid=e[u].l+e[u].r>>1;int s=0;if(x<=mid) s+=iaxy(lc,x,y);if(y>mid) s+=iaxy(rc,x,y);return s;
}void slove(){int m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];iuui(1,1,n);while(m--){int op;cin>>op;if(op==1){int x,k;cin>>x>>k;quxq(1,x,x,k);}else{int x,y;cin>>x>>y;cout<<iaxy(1,x,y)<<endl;}}
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

双重偏移量的线段树

P3373 【模板】线段树 2 - 洛谷

P2023 [AHOI2009] 维护序列 - 洛谷

1622. 奇妙序列 - 力扣（LeetCode）

多个偏移量时，可以采取与上面相同的策略，懒标记；建立多个懒标记，然后通过数学推导更新的公式，在对更新的函数（ggxy()）进行改写即可；

线段树节点维护信息:区间和sum,懒标记ig,ff

下传信息，若先乘后加（乘法优先）

设父节点的懒标记为 g 和 k，子节点的懒标记为 ig 和 ff

则 $(x×ig+ff)×g+k(x\times ig + ff)\times g+k$ $=x×(ig×g)+(ff×g+k),=x\times(ig\times g)+(ff\times g+k),$

子节点新的 $i g$ 为 $g×igg\times ig$ ；新的 $ff$ 为 $ff×g+kff\times g+k$ ；

上传信息，计算 sum

设父节点的懒标记为 g 和 k，子节点 sum，则：
$(x1×g+k)+⋯+(xr×g+k)(x_{1}\times g + k) + \cdots + (x_{r} \times g + k)$
$(x_{1} + \cdots + x_{r}) \times g + (r - l + 1) \times k$
$\times g + (r - l + 1) \times k$

为了方便，我们可以单独将计算更新每个点的时候在列出成一个函数（jisr()），用来表示对一个点的值进行更新，并更新该点的懒标记；

void jisr(int u,int k,int g){e[u].s=(e[u].s*g+(e[u].r-e[u].l+1)*k)%M;e[u].ig=e[u].ig*g%M;e[u].ff=(e[u].ff*g+k)%M;
}

注意：下传后，清空懒标记：ig = 1; ff = 0；

void ggxb(int u){jisr(lc,e[u].ff,e[u].ig);jisr(rc,e[u].ff,e[u].ig);e[u].ff=0;e[u].ig=1;
}

剩下的与上面的模板一致，在进行区间修改（quxq()）的时候，达到目标区间时的更新也可以直接调用计算函数（jisr()）；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
#define lb(x) ((x)&(-x))
#define lc u<<1
#define rc u<<1|1
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int M;
struct edge{int l,r,s;int ff,ig;
}e[4*N];
int n,a[N]; void iuui(int u,int l,int r){e[u]={l,r,a[l],0,1};if(l==r) return ;int mid=l+r>>1;iuui(lc,l,mid);iuui(rc,mid+1,r);e[u].s=e[lc].s+e[rc].s;e[u].s%=M;
}void jisr(int u,int k,int g){e[u].s=(e[u].s*g+(e[u].r-e[u].l+1)*k)%M;e[u].ig=e[u].ig*g%M;e[u].ff=(e[u].ff*g+k)%M;
}void ggxb(int u){jisr(lc,e[u].ff,e[u].ig);jisr(rc,e[u].ff,e[u].ig);e[u].ff=0;e[u].ig=1;
}void quxq(int u,int x,int y,int k,int g){if(x<=e[u].l&&e[u].r<=y){jisr(u,k,g);return ;}int mid=e[u].l+e[u].r>>1;ggxb(u);if(x<=mid) quxq(lc,x,y,k,g);if(y>mid) quxq(rc,x,y,k,g);e[u].s=e[lc].s+e[rc].s;e[u].s%=M;
}int iaxy(int u,int x,int y){if(x<=e[u].l&&e[u].r<=y)return e[u].s;ggxb(u);int mid=e[u].l+e[u].r>>1;int s=0;if(x<=mid) s+=iaxy(lc,x,y);s%=M;if(y>mid) s+=iaxy(rc,x,y);s%=M;return s%M;
}void slove(){int m;cin>>n>>m>>M;for(int i=1;i<=n;i++)cin>>a[i];iuui(1,1,n);while(m--){int op;cin>>op;if(op==1){int x,y,k;cin>>x>>y>>k;quxq(1,x,y,0,k);}else if(op==2){int x,y,k;cin>>x>>y>>k;quxq(1,x,y,k,1);}else{int x,y;cin>>x>>y;cout<<iaxy(1,x,y)<<endl;}}
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

两者对比：

	线段树	树状数组
结构	二叉树	阉割掉了一些点的二叉树
空间	`O(4N)`	`O(N)`
时间	`O(logN)`	`O(logN)`
用途	维护区间信息	维护具有结合律且可差分的信息（如加法、乘法、异或等），是线段树能解决问题的子集
性能	代码长，时间常数大	代码短，时间常数小