普通线段树
基于将区间拆分为$O(logn)$区间的并这一思想来实现。其中附加信息的维护方式变化很灵活。
- 区间加。利用懒标记直接维护。
- 区间加&区间乘。两个懒标记同时维护，其中乘法更新要带动加法更新。
- 区间染色。一个懒标记直接覆盖即可。
- 区间gcd。
- 树上。有点类似树剖，直接利用DFS序转化为线性，然后普通维护就好了。
- 维护最小值的位置。query函数的类型作为结构体，每次返回最小值及其位置。
- 利用取模之后缩小一半的性质，一个数$a$最多被模$loga$次。因此暴力做即可。还要需要维护最大值判断不用取模的情况。
Codeforces 292 E. Copying Data
给出两个序列$a,b$。动态对$b$进行修改，修改操作是指定$a$的一段区间$[x,x+k]$，粘贴到$b$的$[y,y+k]$上。单点询问$b$。
如果我们知道某一个位置最后一次是被哪一次操作覆盖的，那么就可以知道这个位置对应的值。
由此问题转化为求解某一个位置最后一次被哪个操作覆盖。这显然是一个区间赋值（染色）问题。利用线段树维护——只需要用懒标记强行覆盖即可。
Codeforces 914 D. Bash and a Tough Math Puzzle
给出一个序列。动态单点更新。每次询问一段区间，并给出一个数字$x$。问能不能通过修改区间内的一个数字，使区间的$gcd=x$。
这道题告诉我gcd也是满足区间性质的。假如一段区间内所有数都是$x$的倍数，那么我可以将其中一个修改为$x$使得所有数的$gcd$为$x$；假如一段区间内只有一个数不是$x$的倍数，那么我可以将那个数修改为$x$使得所有数的$gcd$为$x$；假如一个区间内有超过一个数不是$x$倍数则无解。由此解决这个问题只需要统计区间内有多少个数不是$x$的倍数即可。
我们可以像维护区间和一样来维护区间$gcd$。如果一个区间的$gcd$是$x$的倍数，意味着这里面全是$x$的倍数；否则，继续深究，如果到达叶节点那么直接判断并返回。注意，这样的做法违背了线段树$O(logn)$查询的原则，所以需要做一些优化——一旦总数超过1就跳出。复杂度玄学。
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$，其中$kgeq 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 leq n$
对于每一个$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$，如果上一次出现的位置$<L$，那么它一定只出现一次。于是我们只需要记录每个位置上的数的上一次出现位置，用线段树维护最小值以及最小值的位置即可。
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$，这样才可以直接计算答案。因为题目是在线询问的，所以每一次合并的时候要开点。