【常用模闆】 線段樹區間操作

線段樹

非常簡單的線段樹

區間操作，比單點操作難那麼一點點（一點點？）但是……似乎……并沒有這麼簡單，這麼多的子程式，檢查比寫都難，可我一直把想要求的區間左右端點和目前端點混着用，就一直不過，很尴尬

#include<cstdio>
#include<iostream> 
using namespace std;
int a[110000];
struct tree{
	long long l,r,sum,addi,len;
}st[100000];
void build(int z,int l,int r)
{
	st[z].l=l,st[z].r=r,st[z].len=r-l+1;
	if(l==r)	st[z].sum=a[l];
	else
	{
		int mid=(l+r)/2;
		build(z*2,l,mid);
		build(z*2+1,mid+1,r);
		st[z].sum=st[z*2].sum+st[z*2+1].sum;
	}
}
void down(int x)
{
	st[x*2].addi+=st[x].addi;
	st[x*2+1].addi+=st[x].addi;
	st[x*2].sum+=st[x].addi*st[x*2].len;
	st[x*2+1].sum+=st[x].addi*st[x*2+1].len;
	st[x].addi=0; 
}
void add(int z,int l,int r,int adn)
{
	if(st[z].l==l&&st[z].r==r)
	{
		st[z].addi+=adn;
		st[z].sum+=adn*st[z].len;
		return ;
	}
	if(st[z].addi)	down(z);
	int mid=(st[z].l+st[z].r)/2;   //這裡mdzz，原來寫的 int mid=(l+r)/2
	if(r<=mid)	add(z*2,l,r,adn);
	else if(l>mid)	add(z*2+1,l,r,adn);
	else	add(z*2,l,mid,adn),add(z*2+1,mid+1,r,adn);
	st[z].sum=st[z*2+1].sum+st[z*2].sum;
}
long long check(int z,int l,int r)
{
	int left=st[z].l,right=st[z].r,mid=(left+right)/2;
	if(l==left&&r==right)	return st[z].sum;
	else if(st[z].addi!=0)	down(z);
	
	if(r<=mid)	return check(z*2,l,r);
	else if(l>mid)	return check(z*2+1,l,r);
	else	return	check(z*2,l,mid)+check(z*2+1,mid+1,r);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int u,x,y,addn;
		cin>>u;
		if(u==1)
		{
			cin>>x>>y>>addn;
			add(1,x,y,addn);
		}
		if(u==2)
		{
			cin>>x>>y;
			cout<<check(1,x,y);
		}
	}
	return 0;
}
           

線段樹再見

轉載于:https://www.cnblogs.com/oiersyp/p/6241632.html