普通线段树数组
基于将区间拆分为$O(logn)$区间的并这一思想来实现。其中附加信息的维护方式变化很灵活。函数
区间加。利用懒标记直接维护。 区间加&区间乘。两个懒标记同时维护，其中乘法更新要带动加法更新。 区间染色。一个懒标记直接覆盖便可。 区间gcd。 树上。有点相似树剖，直接利用DFS序转化为线性，而后普通维护就行了。 维护最小值的位置。query函数的类型做为结构体，每次返回最小值及其位置。 利用取模以后缩小一半的性质，一个数$a$最多被模$loga$次。所以暴力作便可。还要须要维护最大值判断不用取模的状况。 Codeforces 292 E. Copying Data优化
给出两个序列$a,b$。动态对$b$进行修改，修改操做是指定$a$的一段区间$[x,x+k]$，粘贴到$b$的$[y,y+k]$上。单点询问$b$。spa
若是咱们知道某一个位置最后一次是被哪一次操做覆盖的，那么就能够知道这个位置对应的值。排序
由此问题转化为求解某一个位置最后一次被哪一个操做覆盖。这显然是一个区间赋值（染色）问题。利用线段树维护——只须要用懒标记强行覆盖便可。继承
Codeforces 914 D. Bash and a Tough Math Puzzle递归
给出一个序列。动态单点更新。每次询问一段区间，并给出一个数字$x$。问能不能经过修改区间内的一个数字，使区间的$gcd=x$。io
这道题告诉我gcd也是知足区间性质的。假如一段区间内全部数都是$x$的倍数，那么我能够将其中一个修改成$x$使得全部数的$gcd$为$x$；假如一段区间内只有一个数不是$x$的倍数，那么我能够将那个数修改成$x$使得全部数的$gcd$为$x$；假如一个区间内有超过一个数不是$x$倍数则无解。由此解决这个问题只须要统计区间内有多少个数不是$x$的倍数便可。扩展
咱们能够像维护区间和同样来维护区间$gcd$。若是一个区间的$gcd$是$x$的倍数，意味着这里面全是$x$的倍数；不然，继续深究，若是到达叶节点那么直接判断并返回。注意，这样的作法违背了线段树$O(logn)$查询的原则，因此须要作一些优化——一旦总数超过1就跳出。复杂度玄学。gc
Codeforces 877 E. Danil and a Part-time Job
给出一棵树，点权为bool。动态询问子树和，同时会对点权进行修改。修改的规则是：选择一棵子树$v$，子树中全部节点的点权都异或1。
用DFS序将问题转化为线性。而后考虑如何完成取反操做。很像Splay里面的那个区间翻转操做，所以咱们的标记的更新时异或1便可。而后将总和与总数做差便可。
Codeforces 383 C. Propagating tree
给出一棵树，有点权，动态查询子树和。其中会对点权进行修改，修改的规则是：选择一颗子树$v$，给$v$这个点+k，$v$的直接儿子-k，$v$的孙子+k……以此类推。
首先利用树的DFS序转化为线性问题。关键在于分层有正负的问题。虽然哪一层正哪一层负不肯定，可是相对正负关系必定是肯定的。咱们能够假设奇数层为正，偶数层为负。假设偶数层要更新为正，则更新一个负数。最后统计的时候依然按照奇数正偶数负的方式来统计就能获得正确答案。这种思想感受仍是很神奇很重要的。
树的深度统计是要放在递归以前作的，这里我写挂了。
Codeforces 438 D. The Child and Sequence
给出一个序列$a_i$（$n \leq 10^5, a_i \leq 1e9$），动态询问区间和，单点修改，修改操做是区间取模。
区间取模貌似不能直接维护。事实上咱们能够暴力，加上一点小小的优化。假设咱们要让一段区间对$P$取模。那么若是区间内的最大值小于$P$，那么可忽略此操做。另外咱们发现，一个数取模之后至少缩小一半。由此$a_i$最多被模$loga_i$次。由此，复杂度近似是$O(nlognlog1e9)$。
取模以后缩小一半的性质证实：设$a%b=c$，其中$a>b>c$。可表示为$a=kb+c$，其中$k\geq 1$。由于$b>c,k \geq 1$，因此$kb>c$。因此$a>2c$
主席树
单点更新仅产生$O(logn)$个点。故复杂度为$O(mlogn)$
（一）维护区间第$k$小。经过维护区间内每一个数的出现次数，而后在线段树上二分实现。所谓区间，就是指两个历史版本的差。这里利用了前缀和的思想。
（二）维护树上路径上的第$k$小。转化为路径上每一个数的出现次数。利用树上差分的思想。
Codeforces 961 E. Tufurama
给出一个序列$a_i$（$a_i \leq 1e9$），问有多少对$(x,y)$知足$a_x \geq y$且$a_y \geq x$。其中$1 \leq x
对于每个$y$，考虑$x∈[1,y-1]$。那么$x$要知足的条件有$x \leq a_y$，$a_x \geq y$。由前者结合前提可得$x∈[1,min\{y-1,a_y\}]$。
至此，问题转化为求解$x∈[1,min\{y-1,a_y\}]$里，$a_x \geq y$的$x$个数。这是一个求解区间大于$k$的个数问题，利用主席树解决便可。注意须要离散化，细节不少。
一类特殊的出现次数问题
Codeforces 813 E. Army Creation
给出一个序列$a_i$（$n,a_i \leq 10^5$），动态询问区间内元素的最大个数，知足相同元素不超过$k$个。
不能维护每一个元素出现次数，这样的话很是难$log(n)$统计答案。这里有一个巧妙的转化：预处理出$a_i$以后的第$k$个元素的位置，记为$b_i$。若是$b_i \leq r$，那么就不选$a_i$；若是$b_i > r$，那么就选。这样很巧妙地限制了一段区间内咱们最多只取靠后的$k$个相同元素。所以咱们利用$b_i$创建主席树，问题转化为求解区间内大于$r$的元素个数，至关于求$(r,+\infty)$的区间和。
luogu 1972 HH的项链
给出一个序列$a_i$（$n,a_i \leq 5·10^5$），动态询问区间不一样的元素个数。
容易发现这就是上面那题$k=1$的特殊状况。理论上直接主席树解决便可。
但咱们考虑一种线段树的离线作法。对于一个区间的右边界，若是咱们只统计每种元素最靠近右边界的那个位置，就不会重复了，这样区间和就是不一样元素的个数了。咱们能够这样解决：预处理出与$a_i$相等的元素上一次出现的位置$las_i$。将全部询问区间按照右端点排序，用线段树维护每一个位置，0表示不算，1表示算。右端点往右扩展时，碰到的这个数若是以前出现过，就在先前那个位置将1改成0。这样就保证了只统计最靠后的。
Codeforces 1000 F. One Occurrence
给出一个序列$a_i$（$n,a_i \leq 5·10^5$），动态询问一个区间内只出现一次的数（多解可任意）。
考虑线段树离线（或主席树）。咱们一样只考虑最靠近右边界的，对于这样的$a_i$，若是上一次出现的位置$
Codeforces 833 B. Bakery
给出一个序列$a_i$（$n,a_i \leq 35000$），要求把序列划分为$k$段（$k \leq 50$），每段的价值为其中不一样的数的个数。求最大总价值。
明显是一个划分DP的模型。有$dp_{i,j}=max\{dp_{k,j-1}+distinct(k+1,i)\}$。直接转移须要枚举$k$，复杂度就是$O(kn^2)$级别的。所以须要考虑别的方法。
考虑已知$dp_{k,j-1}$，要考虑它对转移的贡献就是要求出全部的$distinct(k+1,i)$。考虑对于区间$(k,i]$内的一个位置$p$能不能对它产生贡献——一种数值的数最多只能产生一个贡献，不如规定最左侧的数产生贡献。这就让咱们联想到去维护一个$pre_p$，咱们只考虑$pre_p \leq k$的位置。针对这种问题，咱们让每个$p$去覆盖区间$[pre_p,p)$。因而位置$k$被覆盖了几回就表明了$distinct(k+1,i)$。用线段树维护区间修改和最大值查询便可。
总结
这类要维护区间内出现了多少个不一样的数的问题，咱们的处理方法都是：对于重复的元素，只看其中一个。或是最左侧的，或是最右侧的。判断最左最右的方法就是维护一个$pre$或者$nxt$数组。线段树维护的通常是位置，附加值表示这个位置算不算或者总共被后面覆盖几回之类的。
可持久化数组
可经过主席树来维护。数组就是主席树的叶节点，上面那些节点实际上是不存放附加信息的。
线段树合并
在树上要求解各子树的答案时，而且用线段树维护时，要合并子树的信息来获得整个树的信息，这时就要用到线段树合并。
线段树合并的思想很简单，就是合并。考虑到空间的限制，要求动态开点（时空复杂度$O(n \log n)$）
当合并根节点为$a,b$的两个线段树时，有两种代码实现的方法。一种是直接将合并后的结果放在$a$上，一种是每次合并新开一个节点做为新的根。对于题目仅仅要咱们输出一次每一个节点的答案时，可使用第一种方法，由于咱们不须要历史信息。而若是题目是在线的屡次询问，那么此时显然须要利用到历史信息的，此时就要选择方法二了。由于第一种方法咱们会在合并的时候直接继承某一个子树，这样在modify操做的时候就会直接影响到历史的线段树致使答案错误了。
Codeforces 600 E. Lomsat gelral
给出一颗树，每一个节点有一个颜色。询问每一个子树内颜色数量最多的那些颜色的总和（颜色的值）
用线段树维护最大值，再附加维护全部最大值的颜色总和。线段树合并便可。
luogu 3605 Promotion Counting
给出一颗树，每一个点有一个权值。询问每一个节点，其全部子树内的节点中权值比它大的节点个数。
离散化后，权值线段树维护和，线段树合并便可。
luogu 3899 谈笑风生
给出一棵树，每次询问一个$a$节点，问有多少个有序数对$(a,b,c)$，知足$a,b$都是$c$的祖先，且$a,b$之间距离不超过$k$
显然要用线段树来维护某一个深度的节点，关键是维护什么？咱们发现应该维护每一个深度的$size$，这样才能够直接计算答案。由于题目是在线询问的，因此每一次合并的时候要开点。