专栏文章

线段树-基础

FFishen
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir2cgew
此快照首次捕获于
2025/12/04 14:36
3 个月前
此快照最后确认于
2025/12/04 14:36
3 个月前
查看原文

线段树是什么？

线段树可以理解为一个二叉树，它将一个序列变成了一棵树状的结构，通过二叉树的一些性质，我们可以优化维护序列区间的时间复杂度，将 O(n)O(n) 复杂度的操作变为 O(logn)O(log n)。
将序列组织成树状结构

模板：

线段树的模板（建立树，单点查、修，区间查、修）
码量较多，因为有较多的操作。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000010;

ll a[maxn],w[maxn*4],lzy[maxn*4];//lzy为延迟标记数组(lazy_tag)

bool InRange(int L,int R,int l,int r){
	//工具：[L,R]是否被[l,r]包含 
	return (l<=L)&&(R<=r); 
} 
bool OutofRange(int L,int R,int l,int r){
	//工具：[L,R]是否和[l,r]完全无交集 
	return (L>r)||(R<l); 
} 
void maketag(int u,int len,ll x){
	//工具：延迟标记 
	lzy[u]+=x;//打标记 
	w[u]+=len*x;//修改当前节点区间和，len个x相加
}
void pushdown(int u,int L,int R){
	//工具：标记下方（把自己的延迟标记下放到子节点） 
	int M=(L+R)/2;
	maketag(u*2,M-L+1,lzy[u]);//给左子树加上lzy[u]
	maketag(u*2+1,R-M,lzy[u]);//给右子树加上lzy[u]
	lzy[u]=0;//去掉自己的标记 
} 
void pushup(const int u){
	//工具：更新 
	w[u]=w[u*2]+w[u*2+1];//当前节点=左子节点+右子节点。
	//这里就是在不断求和 
} 

void build(const int u,int L,int R){//操作：建立树 
	if(L==R){//到达叶节点 
		w[u]=a[L];//w[u]=数组a[L]的值 
		return;
	} 
	int M=(L+R)/2;
	build(u*2,L,M);build(u*2+1,M+1,R);//往左、右区间走 
	pushup(u);//更新当前区间的和。
	//类似回溯 
} 

ll query1(int u,int L,int R,int p){//操作：单点查询（但用线段树做多此一举） 
	if(L==R){
		return w[u];//找到叶结点就返回 
	}else{
		int M=(L+R)/2;//二分查找这一个坐标
		if(M>=p)return query1(u*2,L,M,p);
		else return query1(u*2+1,M+1,R,p); 
	} 
	//复杂度O(log n),如果就用数组O(1) 
} 

ll update1(int u,int L,int R,int p,ll x){//操作：单点修改(修改成x) 
	if(L==R)w[u]=x;
	else{//二分，没有什么好说的 
		int M=(L+R)/2;
		if(M>=p)update1(u*2,L,M,p,x); 
		else update1(u*2+1,M+1,R,p,x);
	}
	//和单点查一样，复杂度O(log n),如果就用数组O(1) 
}

//（接下来才是线段树该做的）
ll query(int u,int L,int R,int l,int r){//操作：区间查
	if(InRange(L,R,l,r))return w[u];//若全部包含则直接返回区间和
	else if(!OutofRange(L,R,l,r)){
		//相交一部分，则递归处理 
		int M=(L+R)/2;
		return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
		//左子节点+右子节点。 
	} 
	else return 0;//没有交集就是0 
} 

void update(int u,int L,int R,int l,int r,ll x){//操作：区间修(改为x) 
	if(InRange(L,R,l,r)){//完全包含 
		maketag(u,R-L+1,x);//直接达标记 
	}else if(!OutofRange(L,R,l,r)){
		int M=(L+R)/2;
		pushdown(u,L,R);//标记下传
		update(u*2,L,M,l,r,x);//左 
		update(u*2+1,M+1,R,l,r,x);//右
		pushup(u);//修改过后要更新（跟单点修一样） 
	}
}

int main(){
  //根据题做操作
	return 0;
}

建立树(也可以用 update)：

CPP
ll a[maxn],w[maxn*4];

void pushup(const int u){
	w[u]=w[u*2]+w[u*2+1];
} 

void build(const int u,int L,int R){
	if(L==R){
		w[u]=a[L];
		return;
	} 
	int M=(L+R)/2;
	build(u*2,L,M);build(u*2+1,M+1,R);
	pushup(u);
}

区间查：

CPP
ll a[maxn],w[maxn*4];

void pushup(const int u){
	w[u]=w[u*2]+w[u*2+1];
} 
bool InRange(int L,int R,int l,int r){
	return (l<=L)&&(R<=r); 
} 
bool OutofRange(int L,int R,int l,int r){
	return (L>r)||(R<l); 
}

ll query(int u,int L,int R,int l,int r){
	if(InRange(L,R,l,r))return w[u];
	else if(!OutofRange(L,R,l,r)){
		int M=(L+R)/2;
		return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
	} 
	else return 0;
}

区间修：

CPP
ll a[maxn],w[maxn*4],lzy[maxn*4];

void pushup(const int u){
	w[u]=w[u*2]+w[u*2+1];
} 
void maketag(int u,int len,ll x){
	lzy[u]+=x;
	w[u]+=len*x;
}
void pushdown(int u,int L,int R){
	int M=(L+R)/2;
	maketag(u*2,M-L+1,lzy[u]);
	maketag(u*2+1,R-M,lzy[u]);
	lzy[u]=0;
}

void update(int u,int L,int R,int l,int r,ll x){
	if(InRange(L,R,l,r)){
		maketag(u,R-L+1,x);
	}else if(!OutofRange(L,R,l,r)){
		int M=(L+R)/2;
		pushdown(u,L,R);
		update(u*2,L,M,l,r,x);
		update(u*2+1,M+1,R,l,r,x);
		pushup(u);
	}
}

例题

P3372【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：
  1. 将某区间每一个数加上 kk。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n,mn, m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：
  1. 1 x y k：将区间 [x,y][x, y] 内每个数加上 kk。
  2. 2 x y：输出区间 [x,y][x, y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1
CPP
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
样例输出 #1
CPP
11
8
20

提示

对于 30%30\% 的数据：n≤8n \le 8，m≤10m \le 10。
对于 70%70\% 的数据：n≤103n \le {10}^3，m≤104m \le {10}^4。
对于 100%100\% 的数据：1≤n,m≤1051 \le n, m \le {10}^5。
保证任意时刻数列中所有元素的绝对值之和 ≤1018\le {10}^{18}。
如果你想省一些码量，可以不写 build 操作，使用 update 每次修改一个点(长度为一的区间)，复杂度为 O(nlogn)O(n log n)

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000010;

ll a[maxn],w[maxn*4],lzy[maxn*4];//lzy为延迟标记数组(lazy_tag)

bool InRange(int L,int R,int l,int r){
	//[L,R]是否被[l,r]包含 
	return (l<=L)&&(R<=r); 
} 
bool OutofRange(int L,int R,int l,int r){
	//[L,R]是否和[l,r]完全无交集 
	return (L>r)||(R<l); 
} 
void maketag(int u,int len,ll x){
	//延迟标记 
	lzy[u]+=x;//打标记 
	w[u]+=len*x;//修改当前节点区间和，len个x相加
}
void pushdown(int u,int L,int R){
	//标记下方（把自己的延迟标记下放到子节点） 
	int M=(L+R)/2;
	maketag(u*2,M-L+1,lzy[u]);//给左子树加上lzy[u]
	maketag(u*2+1,R-M,lzy[u]);//给右子树加上lzy[u]
	lzy[u]=0;//去掉自己的标记 
} 
void pushup(const int u){
	//更新区间和
	w[u]=w[u*2]+w[u*2+1];//当前节点=左子节点+右子节点。
	//这里就是在不断求和 
} 

ll query(int u,int L,int R,int l,int r){//操作：区间查
	if(InRange(L,R,l,r))return w[u];//若全部包含则直接返回区间和
	else if(!OutofRange(L,R,l,r)){
		//相交一部分，则递归处理 
		int M=(L+R)/2;
		return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
		//左子节点+右子节点。 
	} 
	else return 0;//没有交集就是0 
} 

void update(int u,int L,int R,int l,int r,ll x){//操作：区间修(改为x) 
	if(InRange(L,R,l,r)){//完全包含 
		maketag(u,R-L+1,x);//直接达标记 
	}else if(!OutofRange(L,R,l,r)){
		int M=(L+R)/2;
		pushdown(u,L,R);//标记下传
		update(u*2,L,M,l,r,x);//左 
		update(u*2+1,M+1,R,l,r,x);//右
		pushup(u);//修改过后要更新（跟单点修一样） 
	}
}
int main() {
 	int n,m;
 	cin>>n>>m;
 	for(int i = 1;i<=n;++i) {
 		ll val;cin>>val;
 		update(1,1,n,i,i,val);//另一种建树的方法。
	}
 	for(int i=1;i<=m;++i) {
 		int opt;cin>>opt;
 		if(opt==1) {
 			int x,y;ll k;
 			cin>>x>>y>>k;
 			update(1,1,n,x,y,k);//区间修 
 		}else{
 			int x, y;
 			cin>>x>>y;
 			printf("%lld\n", query(1,1,n,x,y));//区间查 
 		}
 	}
 	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...