线段树详解

线段树思想简单，代码略长，不会给读者带来不良感受，请放心食用（滑稽）

好的我们回到正题，线段树这个东西，它是一棵二叉树，用途就是维护一个数列，那么怎么维护呢？它的思想类似于分治，分而治之，首先，这棵树的每一个节点有两个属性，l和r，表示自己管理的范围，那么这棵树的根，它的l和r自然就是1和n（n就是数列的长度），然后，每个节点有两个儿子，分别管理 自己要管理的范围 的1/2 ，拿根节点做例子，根节点要管理1~n，那么它的左儿子就管理1~n/2，右儿子管理n/2+1~n，再记录一下自己左右儿子是谁，这棵树就建好了，比如有一个数列n=4，那么建出来的树就是这个样子的：

可以发现，建完树之后，叶子节点的管理范围只有一，那么他们管理的也就只有在数列中那个位置的数

建树代码：

void buildtree(int x,int y)
{
    len++;
    tree[len].l=x;
    tree[len].r=y;
    tree[len].zuo=tree[len].you=-1;
    tree[len].late=0;//late标记下面会讲
    if(x==y)tree[len].sum=a[x];//sum表示在数列中它管理范围内的数的和
    else
    {
        int now=len;
        int mid=(x+y)/2;//将自己的管理区间分给两个儿子（分）
        tree[now].zuo=len+1;buildtree(x,mid);
        tree[now].you=len+1;buildtree(mid+1,y);
        tree[now].sum=tree[tree[now].zuo].sum+tree[tree[now].you].sum;//由儿子的值得到自己的值（合并）
    }
}

修改和查询（这里以求区间和为例子）：

修改：修改时，我们只需要看看要修改的区间在当前的节点的左儿子上还是在右儿子上，如果只在某一个儿子上，那么直接去修改那个儿子就好了，但如果在两个儿子上都有，那么就把左儿子管理的那些丢给左儿子，右儿子管理的那些丢给右儿子就好了。

比如当前我们需要让1~2区间+x，那么首先从根节点开始，发现1~2都是在左儿子的管理范围里，于是就去到根的左儿子那里，然后发现左儿子的管理范围刚刚好就是要修改的范围，那么这个时候，我们就不需要继续往下了，只需要将这个点的late+x即可，等我们下一次再访问到这个节点时，我们再把它的late值扔给儿子就好了，那么这样子就可以把修改的时间复杂度从O(nlogn)优化成O(玄学)了。。。

代码如下：

void change(int now,int x,int y,ll z)//now表示现在到了线段树的哪个节点，x和y表示修改范围
{
    if(tree[now].l==x&&tree[now].r==y)//管理范围刚好等于修改范围
    {
        tree[now].late+=z;
        give(now);//分配下去
        return;
    }//假如这个点的管理范围比修改范围要大
    give(now);
    int zuo=tree[now].zuo,you=tree[now].you;
    int mid=(tree[now].l+tree[now].r)/2;
    if(y<=mid)change(zuo,x,y,z);//如果在左儿子那里
    else if(x>=mid+1)change(you,x,y,z);//如果在右儿子那里
    else//加入两边都有，就各自修改
    {
        change(zuo,x,mid,z);
        change(you,mid+1,y,z);
    }
    tree[now].sum+=z*(y-x+1);//！！！自己有（y-x+1）个儿子加了z，那么自己的sum值就要加上（y-x+1）* z
} 

查询：

查询和修改差不多，直接看代码吧：

ll print(int now,int x,int y)//x，y表示要求x到y的区间和
{
    give(now);//分配下去，一定要先分配，想想就知道为什么了
    if(tree[now].l==x&&tree[now].r==y)return tree[now].sum;//假如要求的区间刚好就是这个节点管理的区间，那么只需要返回它的sum就好了
    int zuo=tree[now].zuo,you=tree[now].you;
    int mid=(tree[now].l+tree[now].r)/2;//否则就继续往下找
    if(y<=mid)return print(zuo,x,y);
    else if(x>=mid+1)return print(you,x,y);
    else return print(zuo,x,mid)+print(you,mid+1,y);
}

最后补上give函数：

void give(int x)
{
	int zuo=tree[x].zuo,you=tree[x].you;
	tree[x].sum+=(tree[x].r-tree[x].l+1)*tree[x].late;//自己的管理范围内的数全部都加了tree[x].late，那么自己的值自然就要加上 (管理范围*tree[x].late)
	if(zuo!=-1)//假如有儿子，就把自己的late分配下去
	{
		tree[zuo].late+=tree[x].late;
		tree[you].late+=tree[x].late;
	}
	tree[x].late=0;//清空late标记
}

这就是线段树的模板了，若有疑问可以在评论区留言（顺带一提，用线段树做改点求段时，late标记就用不到了，建议去掉省空间）