数据结构学习笔记

（天坑）大概暑假就能填完了

线段树以及高级的线段树

平面扫描线

二维数点类型总结

李超线段树

杂题

单调队列以及决策单调性优化DP

我也不知道这个为啥能放在数据结构里

普通的单调队列优化dp

形如\(dp_i=\max/\min\{dp_j+cost_j\}+w(l_j\le j<i)\)

其中\(l_j\)单增。

斜率优化dp

形如\(dp_i=\max/\min\{dp_j+cost_j+cost_{i,j}\}+w(j<i)\)

其中\(cost_{i,j}\)是和i，j都有关的二次单项式（如\(sum_i*sum_j\)）之类的

其余决策单调性优化

树上问题

点分治

分治类数据结构

一般的分治

例题

对于任意满足结合律的运算符\(\oplus\)和数列\(b_1\cdots b_N\)，\(Q\)次求\(\bigoplus\limits_{i=L}^Rb_i\)

\(N\le10^5,Q\le10^6\)

整体二分

CDQ分治

启发式合并

其他的数据结构

LCT

并查集

数据结构学习笔记

原文：https://www.cnblogs.com/pmt2018/p/12234506.html