数据结构题型整理

注：尚未完成的题目用*标注

树状数组

2492. HH的项链：询问一个区间内有多少不同的数
Codeforces 1553F. Pairwise Modulo

2021 百度之星 预赛 第一场 1006题 二分+树状数组
洛谷P5057 [CQOI2006]简单题 区间01反转–>转化成差分
P2184 贪婪大陆 统计区间被覆盖的线段数量

线段树

Arithmetic Progression 牛客多校第2场 A题*

2021牛客多校第4场E题：Tree Xor *

CF1555E 区间覆盖问题，判断区间有没有被覆盖完全。线段树+双指针

CF240F TorCoder 区间重排，变成字典序最小的回文串（建26棵线段树）
P4588 [TJOI2018]数学计算 直接模拟会爆longlong，用线段树维护因子，乘法的时候就可以轻松取模了

01反转型：
注意01反转的懒标记一定是^=1!!!

相关问题：线段树的懒标记既有区间推平标记，又有区间反转（0->1,1->0），该如何处理呢？
P5057 [CQOI2006]简单题
CF242E XOR on Segment 区间异或。拆位线段树，20棵线段树分别存每一位的情况

CF620E New Year Tree 求区间种类数。树的dfs序+状压存储种类信息

CF438D The Child and Sequence 势能线段树+区间取模，用log的复杂度实现单点暴力修改

Codeforces 431E. Chemistry Experiment（动态开点线段树） 权值线段树+动态开点。注：作为动态开点线段树的模板题

P1438 无聊的数列 线段树维护差分，数字不易维护，但是发现相邻数字的差分易于维护，通过差分就可以快速求出某个位置的值

P2894 [USACO08FEB]Hotel G 区间最长连续1的个数，查询的时候类似二分的思想，如果左边够就优先去左边查询，保证获得的左端点最小

Codeforces 1114F. Please, another Queries on Array?（线段树+区间乘积的欧拉函数） 求区间乘积的欧拉函数

P4145 上帝造题的七分钟 2 / 花神游历各国 势能线段树+区间开方，1e12的数最多只能被开方6次。学习一下log复杂度暴力单点修改的方法，类似CF438D The Child and Sequence 一题

P6327 区间加区间sin和 维护区间sin值（有点意思）

DZY Loves Fibonacci Numbers 斐波那契性质$f_{n+m}=f_{n+1}f_m+f_nf_{m-1}$，懒标记提取公共信息

Codeforces 515E. Drazil and Park（线段树、环上查询、双参数构成的区间max）  

Codeforces 522D. Closest Equals 查询区间相等的最近的两个数

Codeforces 817F. MEX Queries（两种做法） 线段树+离散化

洛谷 P2824. [HEOI2016/TJOI2016]排序（二分+线段树，非常巧妙的思维题！） 01序列上的排序问题，二分

洛谷 P3437. [POI2006]TET-Tetris 3D （二维线段树） 二维线段树

POJ - 2528 区间染色，求种类个数

HDU 4614. Vases and Flowers 区间中找$k$个空位

PAT ICPC网络赛2. 2021ICPC网络赛第二场：L（势能线段树） 区间乘，求区间欧拉函数的和

吉老师线段树

1、区间最值操作：HDU 5306. Gorgeous Sequence（线段树–区间最值操作例题） 将$a_i$变为$min(a_i,v)$

2、区间最值操作+区间历史最值 洛谷 P6242. 【模板】线段树 3 （吉老师线段树）

动态开点线段树

洛谷 P5459. [BJOI2016]回转寿司 给你一个长度为$n$的序列$a$，现在要从中选出一段子序列$[l,r]$​，使得$L\le \sum_{i=l}^{r} a_i \le R$，求方案数

Codeforces 431E. Chemistry Experiment（动态开点线段树） 权值线段树+动态开点。注：作为动态开点线段树的模板题

扫描线

P5490 【模板】扫描线 扫描线求面积
洛谷 P1856. [USACO5.5]矩形周长Picture （扫描线求周长模板题） 扫描线求周长

HDU 1255. 覆盖的面积（扫描线求覆盖两次以上的面积） 扫描线求覆盖两次以上的面积

线段树合并

洛谷 P4556. [Vani有约会]雨天的尾巴 /【模板】线段树合并    线段树合并模板题

洛谷 P3224. [HNOI2012]永无乡（线段树合并） 并查集

Codeforces 600E. Lomsat gelral（线段树合并、DSU on tree） 线段树合并，记录最大值信息

洛谷 P3521. [POI2011]ROT-Tree Rotations（线段树合并、递归性质、逆序对）

Codeforces 490F. Treeland Tour（线段树合并） 线段树合并求树上最长上升子序列

线段树分裂

洛谷 P5494. 【模板】线段树分裂

树链剖分+线段树

洛谷 P4114. Qtree1（树剖+线段树，边权转点权，查询树上路径最大值）

洛谷 P1505. [国家集训队]旅游 树链剖分、线段树、查树上边权最大值、边权最小值、边权和、区间取相反数

洛谷 P6157. 有趣的游戏（树链剖分、线段树、区间严格次大值） 求区间两个数的最大取模，维护区间严格次大值

洛谷 P3979. 遥远的国度（树链剖分、换根） 换根

DSU on tree

模板题：Codeforces 600E. Lomsat gelral（线段树合并、DSU on tree） 统计每个点子树中出现颜色次数最多的编号之和

可持久化trie

可持久化线段树（主席树）

2021icpc昆明M题 代码：49184870
Codeforces 840D. Destiny 求区间内出现次数超过$k$的数

Count on a tree 求树上某一条路径的第k大数

HDU 4348. To the moon（主席树区间修改）

珂朵莉树

Codeforces 896C. C. Willem, Chtholly and Seniorious（珂朵莉树模板题）

Codeforces 915E. Physical Education Lessons（珂朵莉树）

Codeforces 817F. MEX Queries（两种做法）

FHQ treap

模板题：253. 普通平衡树

求区间翻转 AcWing 2437. Splay

KMP相关算法

AC自动机

trie

HDU 6955. Xor sum（01字典树上找异或和大于等于k的两个数）

Codeforces 706D. D. Vasiliy’s Multiset trie树删点模板题

Splay

树套树

莫队

HDU 6959. zoto：查询区间内一定范围的数有多少种
Codeforces 1000F. One Occurrence 维护区间中只出现过一次的数（用辅助栈）

树链剖分

动态树

DLX

左偏树

后缀数组

后缀自动机

点分治

点分树

CDQ分治

仙人掌