经典模板汇总 - 提高组数据结构

upd at 2020-04-18: 更新了题单,添加了一些比较简单的可持久化数据结构 & 伸展树(应该算是提高组吧。。),相关题目位于后4道。

upd at 2020-05-03: 更新了题单,添加了树上差分(主要是点差分)。同时修改了题单介绍页面。

upd at 2020-06-01: 更新了题单,添加了树套树(越来越不像提 高 组了)

upd at 2021-01-07: 退役之后过来把扫描线去了。

upd at 2021-3-13: 添加了字典树

这些题是提高组数据结构相关的经典题(模板题)。

高级数据结构(提高组)的经典模板题,包括:

注意:有些算法的模板题洛谷没有,只能选择了一些经典题目当作模板题。如果你有更好的题目,欢迎私信本蒟蒻!

感谢

@拥抱渴望者


  1. P1886 - 【模板】单调队列 / 滑动窗口
  2. P2580 - 于是他错误的点名开始了
  3. P3372 - 【模板】线段树 1
  4. P3373 - 【模板】线段树 2
  5. P6242 - 【模板】线段树 3(区间最值操作、区间历史最值)
  6. P3374 - 【模板】树状数组 1
  7. P3368 - 【模板】树状数组 2
  8. P2709 - 【模板】莫队 / 小 B 的询问
  9. P3865 - 【模板】ST 表 & RMQ 问题
  10. P3379 - 【模板】最近公共祖先(LCA)
  11. P3128 - [USACO15DEC] Max Flow P
  12. P3384 - 【模板】重链剖分 / 树链剖分
  13. P3369 - 【模板】普通平衡树
  14. P6136 - 【模板】普通平衡树(数据加强版)
  15. P3391 - 【模板】文艺平衡树
  16. P3834 - 【模板】可持久化线段树 2
  17. P3919 - 【模板】可持久化线段树 1(可持久化数组)
  18. P3402 - 【模板】可持久化并查集
  19. P3380 - 【模板】树套树