动态开点线段树做法

这道题与《线段树模板1》的主要区别在于 $n \le 10^9$ ,但是 $m \le 10^5$ ,这是本篇题解的主要切入点。

优点

不需要预先分配整个线段树的空间，而是在需要时才创建节点;
对于稀疏操作的大规模区间，能节省大量内存;
时间复杂度仍保持 $O (log n)$ ;

数据结构定义

CPP

struct stu
{
	ll l,r,lazy,sum;
	ll ls,rs;
}tree[N];

懒标记下推函数（同时担任build）

比较特殊的点在于动态创建子节点（判断是否为0，是则未创建）

CPP

void down(ll id)
{
	stu &a=tree[id];
	if(a.l==a.r) return ;
	ll mid=a.l+(a.r-a.l>>1);
	if(a.ls==0)//无左儿子
	{
		a.ls=++cnt;
		stu &b=tree[cnt];
		b.l=a.l;
		b.r=mid;
		b.sum=init(a.l,mid);
		b.lazy=0;
		b.ls=b.rs=0;
	}
	stu &l=tree[a.ls];
	l.lazy+=a.lazy;
	l.sum+=(l.r-l.l+1)*a.lazy;
	if(a.rs==0)//无右儿子
	{
		a.rs=++cnt;
		stu &b=tree[cnt];
		b.l=mid+1;
		b.r=a.r;
		b.sum=init(mid+1,a.r);
		b.lazy=0;
		b.ls=b.rs=0;
	}
	stu &r=tree[a.rs];
	r.lazy+=a.lazy;
	r.sum+=(r.r-r.l+1)*a.lazy;
	a.lazy=0;
	return ;
}

剩余部分与传统线段树相同;

时间复杂度分析

单次更新和查询操作需要遍历线段树，时间复杂度为 $O (log n)$
整体时间复杂度为 $O (m logn)$ ，其中 $m$ 是操作次数

空间复杂度分析

由于使用了动态开点，空间复杂度取决于实际操作涉及的节点数量，最坏情况下为 $O (m log n)$ ;

最后附上AC代码

至于这里 $N=10^7+10$ 是主包试了很久调试出来的，如有更好的方案还请大佬指教;

CPP

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=1e7+10;
ll n,m,i,cnt=1;
struct stu
{
	ll l,r,lazy,sum;
	ll ls,rs;
}tree[N];
ll init(ll l,ll r)
{
	return (r*(r+1)>>1)-(l*(l-1)>>1);
}
void down(ll id)
{
	stu &a=tree[id];
	if(a.l==a.r) return ;
	ll mid=a.l+(a.r-a.l>>1);
	if(a.ls==0)//无左儿子
	{
		a.ls=++cnt;
		stu &b=tree[cnt];
		b.l=a.l;
		b.r=mid;
		b.sum=init(a.l,mid);
		b.lazy=0;
		b.ls=b.rs=0;
	}
	stu &l=tree[a.ls];
	l.lazy+=a.lazy;
	l.sum+=(l.r-l.l+1)*a.lazy;
	if(a.rs==0)//无右儿子
	{
		a.rs=++cnt;
		stu &b=tree[cnt];
		b.l=mid+1;
		b.r=a.r;
		b.sum=init(mid+1,a.r);
		b.lazy=0;
		b.ls=b.rs=0;
	}
	stu &r=tree[a.rs];
	r.lazy+=a.lazy;
	r.sum+=(r.r-r.l+1)*a.lazy;
	a.lazy=0;
	return ;
}
void update(ll id,ll l,ll r,ll v)
{
	stu &a=tree[id];
	if(a.l>r||a.r<l) return;
	if(a.l>=l&&a.r<=r)
	{
		a.lazy+=v;
		a.sum+=(a.r-a.l+1)*v;
		return ;
	}
	down(id);
	update(a.ls,l,r,v);
	update(a.rs,l,r,v);
	a.sum=tree[a.ls].sum+tree[a.rs].sum;
}
ll query(ll id,ll l,ll r)
{
	if(tree[id].l>r||tree[id].r<l) return 0;
	if(tree[id].l>=l && tree[id].r<=r)
		return tree[id].sum;
	down(id);
	return query(tree[id].ls,l,r)+query(tree[id].rs,l,r);
}
int main()
{
	scanf("%llu%llu",&n,&m);
	stu &a=tree[1];
	a.l=1;a.r=n;
	a.sum=init(1,n);
	a.lazy=0;
	a.ls=a.rs=0;
	while(m--)
	{
		ll q,x,y,z;
		scanf("%llu",&q);
		if(q==1)
		{
			scanf("%llu%llu%llu",&x,&y,&z);
			update(1,x,y,z);
		}
		else
		{
			scanf("%llu%llu",&x,&y);
			printf("%llu\n",query(1,x,y));
		}
	}
	return 0;
}

谢谢，还请大佬指教！

题解：P13825 线段树 1.5

文章操作

动态开点线段树做法

优点

数据结构定义

懒标记下推函数（同时担任build）

时间复杂度分析

空间复杂度分析

最后附上AC代码

相关推荐

评论

题解：P13825 线段树 1.5