近两天主要看的线段树方面的题目。然后发现用到线段树的题目虽然有各种类型，但追其根本都是为了降低时间复杂度，两种本质：一种是单点修改区间查询，另一种是区间修改区间查询操作。只要题目的本质涉及到这两种操作，都可以是用线段树来解决。其实难点主要是考虑线段树每个节点维护什么信息，还有如何通过线段树维护的节点信息来解决题目所要求的问题。从而修改写出build,pushup,update,query四个函数来维护各种信息。
至于最近的数据结构部分，线段树是比赛中很常用到并且变形程度较大的一种。题目可以千变万化，自己要抓其本质联系到线段树的用节点维护信息。所以应该多见题目。形成一种反射，否则很难做出这一类的题目。
总之线段树这个算法是个难点，还要多看题，多思考。
扫一扫
16万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
