在信息学竞赛中，经常遇到这样一类问题：这类问题通常可以建模成数轴上的问题或是数列的问题，具体的操作一般是每次对数轴上的一个区间或是数列中的连续若干个数进行一种相同的处理。常规的做法一般依托于线性表这种数据结构，导致了处理只能针对各个元素逐个进行，因此算法的效率较低。
线段树是一种能够有效处理区间操作的高级数据结构，利用这种数据结构，我们能够设计出针对上述问题更加高效的算法。
线段树的题目通常比较明显，一般一个很明显的特征是m次对某一区间长度的查询。或者是修改。所以我们通常需要的只是将线段树的模型稍加修改，进而套入题目中即可。
模板：
对单个点的修改，和对一段区间的查询：
Read full article from c++ 线段树总结 - Easy sir - 博客园
No comments:
Post a Comment