セグメントツリーテンプレートの要約(✩˙Ⱉ˙ฅ)

うん、下書き箱の中の3編のかわいそうなのを見て...この1編をグーしないでほしい....(｀・ω・´)
一.ツリーを作成

単点修正+クエリー合計のツリー

void push_up(int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void build(int rt,int l,int r)//  
{
	if(l == r)
	{
		sum[rt] = a[l];
		return;
	}
	int m = (l+r)>>1;
	build(rt << 1,l,m);// 
	build(rt <<1|1,m+1,r);//  
	push_up(rt);
}

2.単点修正+クエリー区間最大中のツリーはpush_を変更するだけback関数の内容、残りは変わらない

void push_up(int rt)
{
	sum[rt] = max(sum[rt<<1], sum[rt<<1|1]);//  
}

3.区間クエリのツリーを作成するにはlazy配列の初期化を追加するだけです

void build(int rt,int l,int r)//  
{
	lazy[rt] = 0;
	if(l == r)
	{
		sum[rt] = a[l];
		return;
	}
	int m = (l+r)>>1;
	build(rt << 1,l,m);// 
	build(rt <<1|1,m+1,r);//  
	push_up(rt);
}

二.変更(増減)

単点修正

void update(int rt,int l,int r,int p,int v,bool judge)//  
{
	if(l == r)
	{
		if(judge)
		sum[rt] += v;
		else
		sum[rt] -= v;
		return;
	}
	int m = (l+r) >> 1;
	if(p <= m)
	update(rt << 1,l,m,p,v,judge);
	else
	update(rt << 1|1,m+1,r,p,v,judge);
	push_up(rt); 
}

2.区間修正

void push_down(int rt,int l,int r)
{
	if(lazy[rt])
	{
		int m = (l+r) >> 1;
		lazy[rt << 1] += lazy[rt];
		lazy[rt << 1|1] += lazy[rt];
		sum[rt << 1] += lazy[rt]*(m-l+1);
		sum[rt << 1|1] += lazy[rt]*(r-m);
		lazy[rt] = 0;
	}
}
void update(int rt,int l,int r,int ll,int rr,int v)//  
{
	if(ll <= l&&r <= rr)
	{
		lazy[rt] += v;
		sum[rt] += v*(r-l+1);
		return;
	}
	push_down(rt,l,r);
	int m = (l+r) >> 1;
	if(ll <= m)
	{
		update(rt << 1,l,m,ll,rr,v);
	}
	if(rr > m)
	{
		update(rt << 1|1,m+1,r,ll,rr,v);
	}
	push_up(rt);
}

三.置換

単点置換

void update(int rt,int l,int r,int p,int v)//  
{
	if(l == r)
	{
		sum[rt] = v;
		return;
	}
	int m = (l+r) >> 1;
	if(p <= m)
	update(rt << 1,l,m,p,v);
	else
	update(rt << 1|1,m+1,r,p,v);
	push_up(rt); 
}

2.区間置換

void push_down(int rt,int l,int r)
{
	if(lazy[rt])
	{
		int m = (l+r) >> 1;
		lazy[rt << 1] = lazy[rt];
		lazy[rt << 1|1] = lazy[rt];
		sum[rt << 1] = lazy[rt]*(m-l+1);
		sum[rt << 1|1] = lazy[rt]*(r-m);
		lazy[rt] = 0;
	}
}
void update(int rt,int l,int r,int ll,int rr,int v)// 
{
	if(ll <= l&&r <= rr)
	{
		lazy[rt] = v;
		sum[rt] = v*(r-l+1);
		return;
	}
	push_down(rt,l,r);
	int m = (l+r) >> 1;
	if(ll <= m)
	{
		update(rt << 1,l,m,ll,rr,v);
	}
	if(rr > m)
	{
		update(rt << 1|1,m+1,r,ll,rr,v);
	}
	push_up(rt);
}

四.検索

単点置換/修正の合計クエリー

int query(int rt,int l,int r,int ll,int rr)
{
	if(ll <= l && r <= rr)
	return sum[rt];
	
	int res = 0;
	int m = (l+r) >> 1;
	if(ll <= m)
	res += query(rt << 1,l,m,ll,rr);
	if(rr > m)
	res += query(rt << 1|1,m+1,r,ll,rr);
	
	return res;//  
}

2.区間置換の合計クエリー

int query(int rt,int l,int r,int ll,int rr)
{
	if(l == r)
	return sum[rt];
	push_down(rt,l,r);
	int res = 0;
	int m = (l+r) >> 1;
	if(ll <= m)
	res += query(rt << 1,l,m,ll,rr);
	if(rr > m)
	res += query(rt << 1|1,m+1,r,ll,rr);
	push_up(rt);
	
	return res;
}

3.区間修正の合計クエリー

int query(int rt,int l,int r,int ll,int rr)
{
	if(l == r)
	return sum[rt];
	
	push_down(rt,l,r);
	long long res = 0;
	int m = (l+r) >> 1;
	if(ll <= m)
	res += query(rt << 1,l,m,ll,rr);
	if(rr > m)
	res += query(rt << 1|1,m+1,r,ll,rr);
	
	return res;//
}

まだ書き終わっていないので、後で帰ってきます(グーグーと言わないようにorzを先に送ります)