线段树模板复习

建树

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

标记下传

void pushdown(int l,int r,int rt)
{
	if(lazy[rt])
	{
		int mid=(l+r)>>1;
		lazy[rt<<1]+=lazy[rt];
		lazy[(rt<<1)|1]+=lazy[rt];
		t[rt<<1]+=lazy[rt]*(mid-l+1);
		t[(rt<<1)|1]+=lazy[rt]*(r-mid);
		lazy[rt]=0;
	}
}

区间增加

void add(int l,int r,int L,int R,int rt,int x)
{
	if(L<=l&&r<=R)
	{
		lazy[rt]+=x;
		t[rt]+=(r-l+1)*x;
		return;
	}
	pushdown(l,r,rt);
	int mid=(l+r)>>1;
	if(L<=mid)add(l,mid,L,R,rt<<1,x);
	if(mid+1<=R)add(mid+1,r,L,R,(rt<<1)|1,x);
	t[rt]=t[rt<<1]+t[(rt<<1)|1];
}

区间查询

int query(int l,int r,int L,int R,int rt)
{
	if(L<=l&&r<=R)return t[rt];
	int res=0;
	pushdown(l,r,rt);
	int mid=(l+r)>>1;
	if(L<=mid)res+=query(l,mid,L,R,rt<<1);
	if(mid+1<=R)res+=query(mid+1,r,L,R,(rt<<1)|1);
	return res;
}