线段树

线段树是一种算法竞赛里常见的数据结构，经常被用来维护区间信息，其可以在$O(logn)$的时间里查询、修改区间信息。

一、建树

线段树将每个区间都划分成左右两个区间，直到不可再分为止，假如建一棵区间为$(1-5)$的线段树，其结构应为下图。

根据线段树的结构，我们可以很轻松的写出线段树的建树函数。

代码实现

时间复杂度$O(nlogn)$

void build(gg l,gg r,gg p) //using gg=long long;
{
	if(l==r) //当只有一个点时将值赋给树节点
	{
		tree[p]=v[l];
		return;
	}
	gg mid=(l+r)/2;
	build(l,mid,p*2);
	build(mid+1,r,p*2+1);
	tree[p]=tree[p*2+1]+tree[p*2]; //求出当前区间的区间和
    return;
}

二、区间查询

处理一次查询时，我们可以递归不断减小当前区间，对于每一次减小区间，我们判断当前区间的左右孩子区间是否与需要求的区间有交集，如果有就递归这个孩子区间，最后得到的返回值即是当前区间的区间和。

代码实现

时间复杂度$O(logn)$

gg getsum(gg l,gg r,gg nl,gg nr,gg p)
{
	if(nl>=l&&nr<=r)  //当前区间为子区间时返回当前区间的区间和
	{
		return tree[p];
	}
	gg mid=(nl+nr)/2,sum=0;
	if(mid>=l)
	{
		sum=getsum(l,r,nl,mid,p*2);
	}
	if(mid+1<=r)
	{
		sum+=getsum(l,r,mid+1,nr,p*2+1);
	}
	return sum;  //返回总区间和
}

三、区间修改

暴力修改$O(n)$的时间复杂度是绝对不能接受的，我们可以维护一个$tag$数组，称为懒惰标记，在要修改的区间打一个懒惰标记，每次需要用到这部分的时候再进行下传操作，就可以实现在$O(logn)$的时间复杂度里修改一段区间！

代码实现

时间复杂度$O(logn)$

void update(gg l,gg r,gg nl,gg nr,gg p,gg k) //k为修改的值
{
	if(nl>=l&&nr<=r)
	{
		tree[p]+=k*(nr-nl+1);
		tag[p]+=k;
		return;
	}
	gg mid=(nl+nr)/2;
	if(tag[p]) //遇到标记后下传
	{
		tree[p*2]+=tag[p]*(mid-nl+1);
		tree[p*2+1]+=tag[p]*(nr-mid);
		tag[p*2]+=tag[p];
		tag[p*2+1]+=tag[p];
		tag[p]=0;
	}
	if(mid>=l)
	{
		update(l,r,nl,mid,p*2,k);
	}
	if(mid+1<=r)
	{
		update(l,r,mid+1,r,p*2+1,k);
	}
	tree[p]=tree[p*2+1]=tree[p*2]; //上传更改
	return;
}

添加懒惰标记后，区间查询也要做出相应的更改

gg getsum(gg l,gg r,gg nl,gg nr,gg p)
{
	if(nl>=l&&nr<=r)  //当前区间为子区间时返回当前区间的区间和
	{
		return tree[p];
	}
	gg mid=(nl+nr)/2,sum=0;
    if(tag[p]) //遇到标记后下传
	{
		tree[p*2]+=tag[p]*(mid-nl+1);
		tree[p*2+1]+=tag[p]*(nr-mid);
		tag[p*2]+=tag[p];
		tag[p*2+1]+=tag[p];
		tag[p]=0;
	}
	if(mid>=l)
	{
		sum=getsum(l,r,nl,mid,p*2);
	}
	if(mid+1<=r)
	{
		sum+=getsum(l,r,mid+1,nr,p*2+1);
	}
    tree[p]=tree[p*2+1]+tree[p*2];
	return sum;  //返回总区间和
}

线段树练习题

LuoGu P3372

LuoGu P1253

LuoGu P3373

感谢阅读！