C++ 数据结构 ¶

线性表 ¶

数组 ¶

链表 ¶

应用：链式前向星

双向链表 ¶

循环链表 ¶

栈 stack ¶

先进先出，后进后出

应用：dfs

队列 queue ¶

应用：bfs

单调队列 deque ¶

优先队列是堆，不属于队列 ¶

前缀和与差分 ¶

前缀和：\(pre_{i}=pre_{i-1}+a_{i}\)

差分：\(b_{i}=a_{i}-a_{i-1}\)

原数组是差分数组的前缀和数组，原数组是前缀和数组的差分数组

图 ¶

存图 ¶

链式前向星、vector

最短路问题 ¶

Kruskal，SPFA

集合 set ¶

可以用于去重

并查集 ¶

可以合并和查找的集合

路径压缩 ¶

减少层级（在查找的过程中）

map¶

键与值的对应

树 ¶

堆 ¶

优先队列 priority_queue ¶

树状数组 ¶

区间查询，单点修改

线段树 ¶

区间修改和查询

懒标记 ¶

先在结点上做标记，而并非真正执行

树链剖分 ¶

把“树”剖分成“链”,dfs 时优先往重儿子走