线段树模板+简短解析

 不多bibi，线段树懂得都懂，会用才是最难的

struct Node
{
	int l,r;
	//int s/Max/Min/.....想要用线段树存的东西，  下文中用X代替
	//int lz   //懒标记，在需要区间修改的题目中使用
}tr[N];

inline void push_up(int s)
{
	//通过子节点更新父节点，要求X能过从子区间推导出来比如：和、最大值、最小值。但是种类数之类的就不行
}
inline void push_down(int s)//专门为区间修改设计
{
	/*if(tr[s].lz)
	{
		tr[s<<1].lz+=tr[s].lz;
		tr[s<<1|1].lz+=tr[s].lz;
		tr[s<<1].X
		tr[s<<1|1].X		//懒标记产生的影响
		tr[s].lz=0;
	}*/
}
void build(int s,int l,int r)//建树,s:结点编号，l和r表示区间，
{
	tr[s]={l,r};
	if(l==r)
	{
		//叶子节点中的X一般直接就等于题目要求中的数组的元素，tr[s].X=a[l];
		return;
	}
	int mid = l+r>>1;
	build(s<<1,l,mid);
	build(s<<1|1,mid+1,r);
	push_up(s);
}
void modify(int s,int p,int v)//单点修改，也可以用区间修改代替
{
	if(tr[s].l==tr[s].r)
	{
		//tr[s].X+=v;			//也取决于存的属性
	}
	int mid = tr[s].l+tr[s].r>>1;
	if(p<=mid)modify(s<<1,p,v);
	if(p>mid)modify(s<<1|1,p,v);
	push_up(s);
}
void modify(int s,int l,int r,int v)//区间修改
{
	if(tr[s].l>=l&&tr[s].r<=r)
	{
		//tr[s].lz+=v;
		//tr[s].X			//懒标记产生的影响
	}
	int mid = tr[s].l+tr[s].r>>1;
	if(l<=mid)modify(s<<1,l,r,v);
	if(r>mid)modify(s<<1|1,l,r,v);
	push_up(s);
}
int get(int s,int l,int r)
{
	if(tr[s].l==tr[s].r)
	{
		//return tr[s].X;			
	}
	push_down(s);//及时更新子节点，防止之后查询有误
	int res = 0;
	int mid = tr[s].l+tr[s].r>>1;
	//if(l<=mid)res+=get(s<<1,l,r);//如果查询的区间包含了左儿子的区间，用左儿子更新返回值，右儿子同理
	//if(r>mid)res+=get(s<<1|1,l,r);//更新方式也可能是：res=max(res,get(,,));之类的
	return res;
}