Skip to main content

线段树

参考资料​

实现​

struct SEG
{
	ll a[N],val[N<<2],tag[N<<2];
	void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
	void push_up(int u){val[u]=val[ls]+val[rs];}
	void push_down(int u,int l,int r)
	{
		gx(ls,tag[u],mid-l+1);
		gx(rs,tag[u],r-mid);
		tag[u]=0;
	}
	void build(int u,int l,int r)
	{
		if(l==r){val[u]=a[l];return;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(u);
	}
	void update(int u,int l,int r,int x,int y,ll v)
	{
		if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
		push_down(u,l,r);
		if(x<=mid)update(ls,l,mid,x,y,v);
		if(y>mid)update(rs,mid+1,r,x,y,v);
		push_up(u);
	}
	ll query(int u,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)return val[u];
		push_down(u,l,r);
		ll res=0;
		if(x<=mid)res+=query(ls,l,mid,x,y);
		if(y>mid)res+=query(rs,mid+1,r,x,y);
		return res;
	}
};

拓展​

线段树优化建图​

  • 咕.

例题​

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

洛谷 P3372 【模板】线段树 1

区间修改 + 区间查询

Reference Code
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=100005;
ll a[N],b[N],s[N];
int id[N],len;
void update(int l,int r,ll v)
{
	int x=id[l],y=id[r];
	if(x==y)
	{
		for(int i=l;i<=r;i++){a[i]+=v;s[x]+=v;}
		return;
	}
	for(int i=l;id[i]==x;i++){a[i]+=v;s[x]+=v;}
	for(int i=r;id[i]==y;i--){a[i]+=v;s[y]+=v;}
	for(int i=x+1;i<y;i++){b[i]+=v;s[i]+=v*len;}
}
ll query(int l,int r)
{
	int x=id[l],y=id[r];
	ll res=0;
	if(x==y)
	{
		for(int i=l;i<=r;i++)res+=a[i]+b[x];
		return res;
	}
	for(int i=l;id[i]==x;i++)res+=a[i]+b[x];
	for(int i=r;id[i]==y;i--)res+=a[i]+b[y];
	for(int i=x+1;i<y;i++)res+=s[i];
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	len=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		id[i]=(i-1)/len+1;
		s[id[i]]+=a[i];
	}
	while(m--)
	{
		int op,x,y;
		ll k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			update(x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			cout<<query(x,y)<<'\n';
		}
	}
	return 0;
}
Last updated on