树链剖分总结

专题任务基本完成,先来讲一下题目概括吧

有至少一半基本是模板题,前面有几道,后面也会出现几道,一开始打模板题,总是会遇见各种奇奇怪怪的错误,但是后面再遇到已经可以随便切了,感觉这种掌握的感觉好爽呀,真的是把它变成了工具,说用就用,不用任何准备调试。

然后中间有几道比较恶心的题目,我都写了题解,思路并不是很难,但是代码极其复杂,主要体现在区间的合并(线段树合并以及树剖各区间之间的合并)。

跨越了那几道恶心题后,就很开心了,后面就是水题了,但是最后两道根本不是树链剖分,可以选择跳过,我做了一道,结果做到自闭了,最终做完还剩90分钟,于是放弃了最后一题。

心得感受:

当初真没想到7天能刷完,虽然当时就是热血澎湃。中途有一天因为陪女朋友玩了一天,于是没做题,不过那天趁着路上的时间看了两道比较恶心的题目。

切题顺序:4+2+0+1+2+2+4=15

第一天因为前面都是模板题,于是很顺利的切了四道,还另外做了别的题,第二天还打了CF。

之后玩完回来,调整状态又是一天,所以进度被严重拖延了,导致最后一天剩下五道题,一个下午加一晚上,切了四道,最后一道弃了。

打完后最大的感受就是线段树打的很熟了,而且开始理解一些本质的东西了,线段树本身是一种分治的思想,如果两半区间的信息可以合并更新整个区间的信息,就可以用线段树维护。

还有就是树链剖分本质就是把树上问题转换成连续区间问题,只是一调链变成logn个连续区间,所以想题一般先想如果是一个一维区间怎么做。

原文地址:https://www.cnblogs.com/mmmqqdd/p/10799700.html