专栏文章

线段树-1

FFunction0816
题解参与者 1已保存评论 0

文章操作

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

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

线段树

简述

线段树博客
如图，将一个线性区间建成一棵树。

可以实现区间修改，以及区间查询。

建树

记录目前节点，以及目前区间；
将懒标签初始化为0，从高到低进建树。
CPP
void tb(long long p,long long l,long long r)
{
	tag[p]=0;//初始化懒标签
	if(l==r)//判断是否为叶子节点
	{
		ans[p]=a[l];
		return ;
	}
	long long mid=(l+r)/2;
	tb(p/2,l,mid);
	tb(p/2+1,mid+1,r);//一分为二，递归儿子
    ans[p]=ans[p/2]+ans[p/2+1];//更新父亲
}
由二叉树的性质可知，一个节点 ii 的儿子分别是 i∗2i*2 （左儿子）和 i∗2+1i*2+1 （右儿子）。
于是一分为二，从左右儿子继续递归。
递归完成后，要将左右儿子的区间和加给父亲。

区间加

从根开始，找所求区间并加 kk 。
CPP
void upd(long ll,long long rr,long long l,long long r,long long p,long long k)
{
	if(ll<=l&&rr>=r)//匹配吗？
	{
		ans[p]+=k*(r-l+1);
		tag[p]+=k;
		return ;
	}
	pd(p,l,r);//传递懒标签
	long long mid=(l+r)/2;
	if(ll<=mid)//向下递归儿子
	{
		upd(ll,rr,l,mid,p*2,k);
	}
	if(rr>mid)
	{
		upd(ll,rr,mid+1,r,p*2+1,k);
	}
	ans[p]=ans[p*2]+ans[p*2+1];
}
先要判断节点对应的区间是否符合要求，然后进行push_down操作，即：
CPP
void pd(long long p,long long l,long long r)
{
	long long mid=(l+r)/2;
	f(p*2,l,mid,tag[p]);//传递给两个儿子
	f(p*2+1,mid+1,r,tag[p]);
	tag[p]=0;//reset懒标签
}
也就是说，push_down把祖先的懒标签向下传递。
f：
本质上就是把懒标签（记录在公共祖先上的增加值）和ans（区间和）更新一下
CPP
void f(long long p,long long l,long long r,long long k)
{
	tag[p]+=k;
	ans[p]+=k*(r-l+1);
}

区间查询

运行方式和区间加一样，从根节点出发，不过不用修改，而是把符合的区间和加入 res 。
CPP
long long qu(long long qx,long long qy,long long l,long long r,long long p)
{
	long long res=0;
	if(qx<=l&&qy>=r)//匹配吗？
	{
		return ans[p];
	}
	long long mid=(l+r)/2;
	pd(p,l,r);//懒标签
	if(qx<=mid)//递归儿子并加入res
	{
		res+=qu(qx,qy,l,mid,p*2);
	}
	if(qy>mid)
	{
		res+=qu(qx,qy,mid+1,r,p*2+1);
	}
	return res;
}

模板

题目见P3372
标程：
CPP
#include<bits/stdc++.h>
using namespace std;

const int N=4e5+7;

long long n,m,op,s,b,c;
long long a[N],ans[N],tag[N];

void tb(long long p,long long l,long long r)
{
	tag[p]=0;
	if(l==r)
	{
		ans[p]=a[l];
		return ;
	}
	long long mid=(l+r)/2;
	tb(p*2,l,mid);
	tb(p*2+1,mid+1,r);
	ans[p]=ans[p*2]+ans[p*2+1];
}

void f(long long p,long long l,long long r,long long k)
{
	tag[p]+=k;
	ans[p]+=k*(r-l+1);
}

void pd(long long p,long long l,long long r)
{
	long long mid=(l+r)/2;
	f(p*2,l,mid,tag[p]);
	f(p*2+1,mid+1,r,tag[p]);
	tag[p]=0;
}

void upd(long ll,long long rr,long long l,long long r,long long p,long long k)
{
	if(ll<=l&&rr>=r)
	{
		ans[p]+=k*(r-l+1);
		tag[p]+=k;
		return ;
	}
	pd(p,l,r);
	long long mid=(l+r)/2;
	if(ll<=mid)
	{
		upd(ll,rr,l,mid,p*2,k);
	}
	if(rr>mid)
	{
		upd(ll,rr,mid+1,r,p*2+1,k);
	}
	ans[p]=ans[p*2]+ans[p*2+1];
}

long long qu(long long qx,long long qy,long long l,long long r,long long p)
{
	long long res=0;
	if(qx<=l&&qy>=r)
	{
		return ans[p];
	}
	long long mid=(l+r)/2;
	pd(p,l,r);
	if(qx<=mid)
	{
		res+=qu(qx,qy,l,mid,p*2);
	}
	if(qy>mid)
	{
		res+=qu(qx,qy,mid+1,r,p*2+1);
	}
	return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
	tb(1,1,n);
	while(m--)
	{
		cin>>op;
		cin>>s>>b;
		if(op==1)
		{
			cin>>c;
			upd(s,b,1,n,1,c);
		}
		else
		{
			cout<<qu(s,b,1,n,1)<<endl;
		}
	}
	return 0;
}
  • 最后要注意一下，线段树在最大的情况下有接近 4n4n 的大小，数组要开够。（求和可别忘了long long欧~）

评论

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

正在加载评论...