典的应用
来引入线段树的概念等一系列问题，即染色问题。PKU_2777为例，以
题目大意是有一块长度为L厘米的板，每厘米可以看成一个单位区间，颜色的种类由数字表示，一开始每个区间的颜色都是1，而现在要对这种树进行O次操作，操作有两种，第一种是将区间A到B的颜色都染成C颜色，第二种是询问区间A到B之间一共有几种颜色。最简单
f的想法可能是开个长度为L的数组a，而ai存的就是第i格的颜色，但是可行吗？我们来看下数据范围，L的范围是十万，O的范围也是十万，那么算法复杂度就是OLO，明显会超时，所以我们选择用线段树来帮助我们解决这个问题，其实线段树这个名词并不能很好地阐述它强大的功能，我更喜欢他的学术名词区间树，同其他的树一样，他可以在OlogL的时间内对树进行维护操作，这也就意味着他可以在OlogL的时间内对一段区间进行一系列的操作。正是线段树这种高效，让他在RMQ问题，以及求矩形合并面积，周长等一系列问题中得到了充分的应用。这里我想讲一下RMQ问题即求区间内最大or最下值的问题，众所周知，RMQ问题有一种ONlogN的预处理以及O1时间求出任意区间内最大or最小值的离线算法（所谓离线，即不能在求的过程中动态地改变或者插入区间的值），即STSparseTable算法，相比之下，线段树并没有效率上的优势，但ST算法有个局限性，就是不支持在线操作，而线段树则没有这种限制，由此可知，线段树的强大。线段树还有一个高级的应用就是对于区间最值信息的维护，相应的经典题有很多，也有一定的难度，PKU_2482，PKU_1151求
个矩形合并后的面积，PKU_1177求
个矩形合并后的边界周长等等。最值的维护要抓住的基本思想就是递归地维护每一颗子树，利用子树的信息去维护父亲。8字符串包括KMP算法Trie树后缀数组字符串处理也是ACM中相当大的一块知识面，而且也具有相当的实
f际应用面，其实对于字符串的知识我自己接触的也比较少，所以只能简单地谈一下几个最为基础的算法，KMP算法是两串匹配最为基础的线性算法，该算法的核心是对于
ext数组的理解，该数组是对于一个串进行了预处理得到的，从而成功将两串匹配的复杂度降到了线性。但KMP算法只能是两串之间的匹配，如果我们要多串匹配的话该怎么办呢？Trie帮助我们解决了这个难题，Trie其实是一颗字母树，树的每个节点都有26个英文字母，通过对这些节点的进行标记来插入一个字符串，在插入了
个字符串之后，我们就可以同时对这
个字符串之后我们r