跳转至

数据结构部分简介

数据结构

  • Q:什么是数据结构?

  • A:简单地讲,数据结构就是数据的储存方式。

  • Q:数据结构有什么用呢?

  • A:对于给定的数据,通过使用不同的数据结构储存,可以获得不同的效果。例如,数组便于快速访问某一特定位置的值,但会在插入、删除操作中浪费大量时间;链表则便于插入、删除单个元素,但用于访问特定位置的效率却不容乐观。线段树,平衡树则可以加速对于特定信息的检索与维护,如区间和,排名等。灵活地使用数据结构可以对代码的运行效率产生不可忽视的影响。

  • Q:在算法竞赛中,数据结构有那些考察点呢?

  • A:算法竞赛中,数据结构的考察主要分为两类:

    ​ 1. 考察对于特定信息的检索与维护和对特定操作的支持,例如「SCOI2010」序列操作

    ​ 2. 使用合适数据结构加速信息检索,优化算法复杂度,例如「APIO2012」派遣

  • Q:有没有一种完美的数据结构可以搞定所有事情啊?

  • A:很遗憾地告知您: 并没有,所以要努力学习下面的内容呢!

  • STL

    • STL 简介

    • vector

    • priority_queue

    • map

    • bitset

  • pb_ds

    • pb_ds 简介

    • __gnu_pbds::priority_queue

  • 队列

  • 链表

  • 哈希表

  • 并查集

    • 堆简介

    • 二叉堆

    • 配对堆

    • 左偏树

  • 块状数据结构

    • 分块思想

    • 块状链表

    • 块状数组

    • 树分块

  • 单调栈

  • 单调队列

  • 倍增

  • 树状数组

  • 线段树

  • 线段树 & 区间历史最值

  • 划分树

  • 平衡树

  • 树套树

  • K-Dtree

  • 可持久化数据结构

  • 珂朵莉树

  • Link Cut Tree

  • Euler Tour Tree

  • 析合树


评论