线段树
|
老官童鞋gogo
|
59
|
0
|
数据结构,程序设计
|

1494 字
|
21 分钟

线段树简介

主要作用：

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

时间复杂度：

每一次查询、修改：$$ O(log N) $$

基本形态：

若用 $ tree[ ] $ 表示树， $ x $ 表示线段树上的节点， $ tree[x] $ 表示节点所表示的区间，那么这个节点的左儿子为 $ tree[x<<1] $ ，右儿子为 $ tree[x<<1|1] $ 。 如图：

线段树形态示意图

——来自于OI Wiki（图片中的$d$数组即为$tree$数组)

不难发现，若 $ tree[x] $ 表示的的区间为 $ [l,r] $ 则他的左儿子所表示的区间为 $ [l,\frac {l+r}{2}] $ ，右儿子所表示的区间为 $ [frac{l+r}{2}+1,r] $ 。

线段树的构造

原理

线段树将每个长度不为 $ 1 $ 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。 容易知道线段树的深度是 $ \lceil \log n \rceil $ 的，则在堆式储存情况下叶子节点（包括无用的叶子节点）数量为 $ 2^{\lceil \log n \rceil} $ 个，又由于其为一棵完全二叉树，则其总节点个数 $ 2^{\lceil \log n \rceil}-1 $ 。所以需要将长度设置为 $ 4n $ 。

代码

void build(int x,int l,int r)
{
    if(l==r) 
    {
        tr[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    tr[x]=tr[x<<1]+tr[x<<1|1];
}

线段树的懒惰标记

现在我们要对一个区间进行修改，如果我们用单点查询的办法一个一个搜索，那复杂度必然是不正确的，这时候我们就要引入懒惰标记。简单来说，就是通过延迟对节点信息的更改，从而减少可能不必要的操作次数。每次执行修改时，我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。 仍然以最开始的图为例，我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个$ t[i] $，表示该节点带的标记值。 最开始时的情况是这样的（为了节省空间，这里不再展示每个节点管辖的区间）：

——来自于OI Wiki

现在我们准备给 $ [3,5] $上的每个数都加上 $ 5 $。根据前面区间查询的经验，我们很快找到了两个极大区间 $ [3,3] $ 和$ [4,5] $（分别对应线段树上的$ 3 $号点和$ 5 $号点）。 我们直接在这两个节点上进行修改，并给它们打上标记：

——来自于OI Wiki我们发现，$ 3 $号节点的信息虽然被修改了（因为该区间管辖两个数，所以$ d_3 $ 加上的数是$ 5 \times 2=10 $），但它的两个子节点却还没更新，仍然保留着修改之前的信息。不过不用担心，虽然修改目前还没进行，但当我们要查询这两个子节点的信息时，我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确。 接下来我们查询一下$ [4,4] $区间上各数字的和。 我们通过递归找到$[3,4] $区间，发现该区间并非我们的目标区间，且该区间上还存在标记。这时候就到标记下放的时间了。我们将该区间的两个子区间的信息更新，并清除该区间上的标记。

——来源于OI Wiki

现在$ 6 $、$ 7 $两个节点的值变成了最新的值，查询的结果也是准确的。

线段树的查询与修改

区间查询，单点修改

来源：洛谷：P3374 【模板】树状数组 1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map> #include<set>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl;
void read()
{
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int tree[2000010],a[2000010];
void build(int x,int l,int r)//建树：x表示当前节点，l表示当前区间的左端点，r表示当前区间的右端点
{
    if(l==r)//当l==r时，表示建树建到了叶子结点，退出递归
    {
        tree[x]=a[l];//a[i]表示原始数据
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);//建立左子树
    build(x<<1|1,mid+1,r);//建立右子树
    tree[x]=tree[x<<1]+tree[x<<1|1];//区间和等于左子树的和加上右子树的和
    return;
}
void add(int x,int l,int r,int pos,int y)//单点修改：x表示当前节点，l表示当前区间的左端点，r表示当前区间的右端点，pos表示当前要修改的数据的位置，y表示要修改多少的值
{
    if(l==r)//找到了叶子结点，即pos点，退出递归
    {
        tree[x]+=y;//这里的+=可以换成其他运算符
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)//若要找的点在自己的左儿子表示的区间中
        add(x<<1,l,mid,pos,y);
    if(pos>mid)//若要找的点在自己的右儿子表示的区间中
        add(x<<1|1,mid+1,r,pos,y);
    tree[x]=tree[x<<1]+tree[x<<1|1];//左右相加
}
int ask(int x,int l,int r,int ql,int qr)//单点查询：x表示当前节点，l表示当前节点表示当前区间的左端点，r表示当前区间的右端点，ql表示要查询的区间的左端点，qr表示要查询的区间的右端点。
{
    if(ql<=l&&r<=qr)//如果当前区间完全包括在要查询的区间的范围内，返回节点的值
        return tree[x];
    int mid=(l+r)>>1;
    int res=0;
    if(ql<=mid)//查询左儿子
        res+=ask(x<<1,l,mid,ql,qr);
    if(qr>mid)//查询右儿子
        res+=ask(x<<1|1,mid+1,r,ql,qr);
    return res;//返回两儿子的值得和
}
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    build(1,1,n);
    while(m--)
    {
        int f=read();
        if(f==1)
        {
            int x=read(),k=read();
            add(1,1,n,x,k);
        }
        else
        {
            int x=read(),y=read();
            cout<<ask(1,1,n,x,y)<<endl; 
        }
    return 0;
}

区间查询，区间修改（仅加法）

来源：洛谷：P3372 【模板】线段树 1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long n,m,a[1000001];
struct Node
{
    long long l,r,sum,lz;
}tree[1000001];
void build(long long i,long long l,long long r)//建树
{
    tree[i].l=l,tree[i].r=r;
    if(l==r)
    {
        tree[i].sum=a[l];
        return;
    }
    long long mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return;
}
void pushdown(long long i)//懒惰标记下推：i表示懒惰标记所在节点
{
    if(tree[i].lz!=0)//判断是否有懒惰标记
    {
        tree[i<<1].lz+=tree[i].lz;//将懒惰标记传递给左右儿子
        tree[i<<1|1].lz+=tree[i].lz;
        long long mid=(tree[i].l+tree[i].r)>>1;
        tree[i<<1].sum+=tree[i].lz*(mid-tree[i<<1].l+1);//修改当前节点的值
        tree[i<<1|1].sum+=tree[i].lz*(tree[i<<1|1].r-mid);
        tree[i].lz=0;
    }
    return;
}
void add(long long i,long long l,long long r,long long k)//区间修改
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);//将要修改的值乘区间元素个数于原数相加得到当前值
        tree[i].lz+=k;//标记懒惰标记
        return;
    }
    pushdown(i);//懒惰标记下移
    if(tree[i<<1].r>=l)
        add(i<<1,l,r,k);
    if(tree[i<<1|1].l<=r)
        add(i<<1|1,l,r,k);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return;
}
long long search(long long i,long long l,long long r)//区间查询
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    pushdown(i);//查询是将懒惰标记下移
    long long s=0;
    if(tree[i<<1].r>=l)
        s+=search(i<<1,l,r);
    if(tree[i<<1|1].l<=r)
        s+=search(i<<1|1,l,r);
    return s;
}
int main()
{
    cin>>n>>m;
    for(long long i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    for(long long i=1;i<=m;i++)
    {
        long long p;
        cin>>p;
        if(p==1)
        {
            long long x,y,k;
            cin>>x>>y>>k;
            add(1,x,y,k);
        }
        else
        {
            long long x,y;
            cin>>x>>y;
            cout<<search(1,x,y)<<endl;
        }
    }
    return 0;
}

区间查询，区间修改（乘法加法混合）

来源：洛谷：P3373 【模板】线段树 2


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long a[10000010],n,m,mod;
struct Node
{
    long long sum,plz,mlz;
}tree[10000001];
void build(long long l,long long r,long long i) {
    tree[i].mlz=1;
    if(l==r)
    {
        tree[i].sum=a[l];
        return;
    }
    long long mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    tree[i].sum%=mod;
}
void pushdown(long long nl,long long nr,long long i) {
    long long mid=(nl+nr)>>1;
    if(tree[i].mlz!=1)//根据优先级，我们需要优先处理乘法的懒惰标记
    {
        tree[i<<1].mlz*=tree[i].mlz,tree[i<<1|1].mlz*=tree[i].mlz;//先乘后加
        tree[i<<1].mlz%=mod,tree[i<<1|1].mlz%=mod;
        tree[i<<1].plz*=tree[i].mlz,tree[i<<1|1].plz*=tree[i].mlz;
        tree[i<<1].plz%=mod,tree[i<<1|1].plz%=mod;
        tree[i<<1].sum*=tree[i].mlz,tree[i<<1|1].sum*=tree[i].mlz;
        tree[i<<1].sum%=mod,tree[i<<1|1].sum%=mod;  
        tree[i].mlz=1;
    }
    if(tree[i].plz)//然后处理加法的
    {
        tree[i<<1].plz+=tree[i].plz,tree[i<<1|1].plz+=tree[i].plz;
        tree[i<<1].plz%=mod,tree[i<<1|1].plz%=mod;
        tree[i<<1].sum+=tree[i].plz*(mid-nl+1),tree[i<<1|1].sum+=tree[i].plz*(nr-mid);
        tree[i<<1].sum%=mod,tree[i<<1|1].sum%=mod;  
        tree[i].plz=0;
    }
}
void mult(long long l,long long r,long long nl,long long nr,long long k,long long i)//乘法修改 {
    if(l<=nl&&r>=nr)
    {
        tree[i].sum=tree[i].sum*k%mod;
        tree[i].mlz=tree[i].mlz*k%mod;
        tree[i].plz=tree[i].plz*k%mod;//需要将加法的懒惰标记一起变更
        return;
    }
    pushdown(nl,nr,i);
    long long mid=(nl+nr)>>1;
    if(l<=mid)
    {
        mult(l,r,nl,mid,k,i<<1);
    }
    if(r>mid)
    {
        mult(l,r,mid+1,nr,k,i<<1|1);
    }
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    tree[i].sum%=mod;
}
void add(long l,long long r,long long nl,long long nr,long long k,long long i)//加法修改 {
    if(l<=nl&&r>=nr)
    {
        tree[i].plz=(tree[i].plz+k)%mod;
        tree[i].sum=(tree[i].sum+k*(nr-nl+1))%mod;
        return;
    }
    pushdown(nl,nr,i);
    long long mid=(nl+nr)>>1;
    if(l<=mid)
    {
        add(l,r,nl,mid,k,i<<1);
    }
    if(r>mid)
    {
        add(l,r,mid+1,nr,k,i<<1|1);
    }
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    tree[i].sum%=mod;
}
long long search(long long l,long long r,long long nl,long long nr,long long i)//查询 {
    if(l<=nl&&r>=nr)
    {
        return tree[i].sum;
    }
    pushdown(nl,nr,i);
    long long mid=(nl+nr)>>1,s=0;
    if(l<=mid)
    {
        s+=search(l,r,nl,mid,i<<1);
    }
    s%=mod;
    if(r>mid)
    {
        s+=search(l,r,mid+1,nr,i<<1|1);
    }
    return s%mod;
}
int main() {
    cin>>n>>m>>mod;
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    for(long long i=1;i<=m;i++)
    {
        long long p;
        scanf("%lld",&p);
        if(p==1)
        {
            long long x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            mult(x,y,1,n,k,1);
        }
        if(p==2)
        {
            long long x,y,k;
            scanf("%lld%lld%lld",&x,&y,&k);
            add(x,y,1,n,k,1);
        } 
        if(p==3)
        {
            long long x,y;
            scanf("%lld%lld",&x,&y);
            long long ans=search(x,y,1,n,1);
            printf("%lldn",ans);
        }
    }
    return 0;
}
文章标题：线段树
文章链接：https://www.laoguantx.top/%e7%ba%bf%e6%ae%b5%e6%a0%91.html
文章内容仅供参考，其中可能会有部分内容参考、引用其他网站，转发请务必标注作者为 “老官童鞋gogo” ，原文链接为 https://www.laoguantx.top/%e7%ba%bf%e6%ae%b5%e6%a0%91.html 。
线段树
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
差分约束

							
							

							
表达式树——初赛

							
							

							
高阶差分

							
							

							
P1265 公路修建 题解

							
							

							
CSP历届初赛知识点总结（1）