图片来源于OI-Wike

线段树大概就是如图的一个数据结构，它基于分治思想，可以解决许多问题（每个点存的是一个范围，每个范围可对应两个小范围，典型的分质）

常见的能用线段树解决的问题包括区间修改，单点修改，区间查询，单点查询（其实就是维护一个序列的动态前缀和），还有 #$*%&的扫描线，总之就是范围非常高的大；

他与树状数组处理的范围很相似，且树状数组做的他也能做，但是树状数组比他更简单，代码量少，所以能用树状数组就用树状数组

线段树优点是容易看出题目要不要用线段树，思考量少，但缺点是代码过长，容易写错，写十五分钟，调一个小时，直接红温

线段树的性质

1.他是有一个范围为$1~n$的节点开始构造而来的，这个点也是他们的根节点

2.叶子结点范围为$\{x,x\}$

3.每个节点左儿子是$\{l,mid\}$，右儿子是$\{mid+1,r\}$,$mid$是$r-l+1$

4.每个节点的子节点在数组里位置为$u/2$，他的做儿子是$2timesu$也是$u<<1$，有儿子是$2\times u+1$也是$u<<1|1$,别问，问就是省常数

来看一下数组要开的范围，说先我们看上面这坨

$$点数=(n/2+n/4+n/8+...)$$

约是:

$$点数=2\times n$$

但他也只是一个完全二叉树，下面也有一点，所以我们尽量开$4\times n$

我们发现，他占空间确实非常的大，然后我们来看一下代码如何：

建树

struct Node{
	int l,r;
	int v;
}tr[N*4];
void pushup(int u){
	tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r){
	if(l==r)tr[u]={l,r,0};
	else{
		tr[u]={l,r,0};
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
    pushup(u);
	}
}

上面的pushup是取他子节点的值，builld就是一直分质向下

修改

void modify(int u,int x,int c)
{
	if(tr[u].l==x&&tr[u].r==x)tr[u]={x,x,c};
	else{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid)modify(u<<1,x,c);
		else modify(u<<1|1,x,c);
		pushup(u);
	}
}

查询

int query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].v;
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(r<=mid)return query(u<<1,l,r);
		else if(l>mid)return query(u<<1|1,l,r);
		else
		{
			int v=0;
			v=query(u<<1,l,r);
			v=max(v,query(u<<1|1,l,r));
			return v;
		}
	}
}

懒标记

又被称为延迟标记，比变的地方在于我们之前是