线段树笔记

void pushup(int tr){
	seg[tr]=seg[tr*2]+seg[tr*2+1];
} 
void build(int tr,int l,int r){
	if(l==r){
		seg[tr]=a[r];
		return ;
	}
	int mid=(l+r)/2;
	build(tr/2,l,mid);
	build(tr/2,mid+1,r);
	pushup(tr);
}
void pushdown(int tr,int l,int r){
	if(pls[tr]==0) return;
	int mid=(l+r)/2;
	pls[tr<<1]+=pls[tr];
	pls[tr<<1|1]+=pls[tr];
	seg[tr<<1]+=(mid-l+1)*pls[tr];
	seg[tr<<1|1]+=(r-mid)*pls[tr];
	pls[tr]=0;
}
void update(int tr,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		seg[tr]+=z*(r-l+1);
		pls[tr]+=z;
		return ;
	}
	pushdown(tr,l,r);
	int mid=(l+r)/2;
	if(x<=mid) update(tr<<1,mid,x,y,z);
	if(y>mid) update(tr<<1|1,mid+1,x,y,z);
	pushup(tr);
}
void query(int tr,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		return seg[tr];
	}
	pushdown(tr,l,r);
	int mid=(l+r)/2;
	if(x<=mid) ans+=query(tr<<1,mid,x,y,z);
	if(y>mid) ans+=query(tr<<1|1,mid+1,x,y,z);
	return ans;
}