注明:目前使用线段树的次数不多,如果细节部分有微小错误,还请在评论区指证,谢谢!
基本认识
线段树是一种常用的数据结构,对于研究算法的acmer来说,更是必不可少。
但是主流的一些教材上,却往往对其避而不谈,例如《算法导论》、《数据结构》等等。
原因是,线段树相对其他常用数据结构来说,使用频率较低,而且难度相对较大。
但是其实一旦理解好了其内部原理,线段树的实现就很简单了。
线段树和区间树有着许多的相似之处,因此了解区间树有利于更好地学习线段树(没有学过也不要紧),线段树就像是区间树的升级版,先难后易也可。
在学习线段树之前,我们首先要明白,为什么线段树在区间数据的修改上有着很大的优势。
例如,给你一个长度为10000的数组,让你进行如下操作,每一次修改一个区间的值,让里面的数字同时加上或者减去一个值,求最后这10000个数的和。
如果用暴力解决,循环修改区间里的数字,当操作的次数增多时,非常容易超时。
但是改用线段树,就能大大减小时间复杂度。
原因是因为线段树不会直接一个个修改区间的值,而是利用一个lazy标记,代替一个区间所需要修改的值,从而减小不必要的复杂度。
当然,可能大家也有过这样的思路,既然是对区间进行操作,那为什么不直接合并区间,最后求和呢?
我自己也试过这样的方法,但是实际执行起来会发现一个问题,为了避免区间的重合,你每一次合并区间,都要查找区间之间是否有重合的部分,造成的结果就是时间复杂度会达到o(n*n).
一旦面临n过大的题目,不可避免的会超时。
线段树实现
前言说完,现在我们来讲讲线段树实现。
看一个结构图(因为懒得自己画就拿了个别人的……):
线段树的源节点是节点1,这一点必须注意,因为数组开始是0,建树的时候必须小心。
使用线段树之前,肯定得有存储结构。
线段树一般存在一维数组中,为了避免越界问题,空间复杂度要开到4n,在下面代码我使用a代表线段树的数组。
同理lazy标记也需要一个4n的数组。
下面的例子以维护区间和为例,但是需要知道的是,线段树不只可以维护区间和,也可以维护例如区间最大值、区间乘积之类的信息。
线段树操作可以分为五个部分,:
buildtree(如果有初始值)
mark(标记一个区间的lazy)
pushdown(向下标记,也就是向左右子树标记)
update(更新一个区间,也就是修改)
query(获取一个区间的求和值)。
总结起来,线段树的实现就是遇到一个区间时,能整体update操作就不少量操作,实在不行就只能pushdown缩小区间,再update操作。做完了就query获取成果。
首先,对于有初始值的题目,我们需要建树,建树的过程中因为涉及到线段树变换,所以需要维护区间和。
补充:线段树是树状结构,poi<<1 表示当前位置的左子树,poi<<1|1表示当前位置的右子树
void buildtree(int* t,int poi,int l,int r)//注意数组要足够长,不要越界
{
if (l == r)
{
a[poi] = t[l];
return;
}
int mid = l + r >> 1;
buildtree(t, poi << 1, l, mid);
buildtree(t, poi << 1 | 1, mid+1, r);
a[poi] = a[poi << 1] + a[poi<< 1 | 1];//建树也不要忘记维护区间和
}
然后是mark操作,将lazy标记传下去,这一步很简单,同样需要维护区间和。
void mark(int poi, int l, int r, int k)
{
a[poi] += (r - l + 1) * k;//维护
lazy[poi] += k;
}
接着是pushdown操作,目的是将当前位置的lazy标记清空并且向子树传,依赖于mark实现。
void pushdown(int poi,int l,int r)
{
int mid = l + r >> 1;
mark(poi << 1, l, mid,lazy[poi]);
mark((poi << 1)+1, mid+1, r, lazy[poi]);
lazy[poi] = 0;
}
然后是update操作,对区间的值进行更新,要注意细节,维护区间和。
void update(int poi, int l, int r,int x,int y,int v)
{
if (x <=l && y >=r)//如果当前区间在想要修改的范围内,就直接修改
{
mark(poi, l, r, v);
return;
}
//不在范围内时,需要对以中间为界两边进行查找
int mid = l + r >> 1;
if (lazy[poi] != 0)//不为0才pushdown,为0 的话pushdown没有意义
pushdown(poi, l, r);
if (x <= mid)
{
update(poi << 1, l, mid,x,y, v);
}
if (y > mid)
{
update((poi << 1) + 1, mid + 1, r,x,y, v);
}
a[poi] = a[poi << 1] + a[(poi << 1) + 1];//维护区间和
}
最后是query操作,获取区间和的结果,方法和update类似,但是多了一个res存储结果。
int query(int poi,int l,int r,int x,int y)
{
int res=0;
if (x <=l && y >=r)
{
return a[poi];
}
int mid = l + r >> 1;
if (lazy[poi] != 0)//不为0才pushdown,为0 的话pushdown没有意义,
pushdown(poi, l, r);
if (x <= mid) res += query(poi << 1, l, mid, x, y);
if (y > mid) res += query((poi << 1) + 1, mid + 1, r, x, y);
return res;
}
整合起来,一个线段树的逻辑就写好啦~
看到这里的小伙伴,恭喜你已经对线段树有了基本的认识!!
所以……
给自己鼓个掌!!!
不过要完全掌握还需要多多练习才行。