数据结构

数据结构类型

• 线性结构
  • 数组
  • 链表
  • 栈
  • 队列
• 树形结构
  • 二叉树
  • 堆
  • B树和B+树
  • Trie树
• 图形结构
• 散列结构

栈

• 单调栈
  • 基本思想：元素入栈前，首先需要弹出栈顶元素，直到栈顶元素不小于（不大于）当前元素，然后再将当前元素入栈。
  • 例：寻找数组元素左边最近的大于当前元素的数

前缀数组

• 前缀和

队列

• 单调队列
  • 使用双端队列，高效维护滑动窗口中的极值
  • 基本思想：
    1. 维持滑动窗口。如果队首元素不在窗口内，则将其弹出。重复操作直到队首元素在窗口内。
    2. 维持单调性。类似于单调栈，元素入队前，首先需要弹出队尾元素，直到队尾元素不小于（不大于）当前元素，然后再将当前元素入队。

链表

• 相交链表
• 环形链表

堆

• 大根堆、小根堆
• 优先队列
  • 查询：直接返回堆顶元素。
  • 插入：插入到末尾，然后向上调整。
  • 删除：堆顶元素与末尾元素交换，然后向下调整。
  • 修改：修改目标元素值，然后向上调整。

ST表

• 高效查询静态区间的最值
• 预处理：st[i][j]表示从位置i开始，长度为2的j次方的区间内的最值。
  • 递推式st[i][j] = max(st[i][j-1], st[i + 2**(j-1)][j-1])
• 查询：
  • 查询区间[L,R]的最值，首先计算k=floor(log2(R-L+1))
  • 再获取结果为max(st[L][k],st[R-2**j+1][k])

树状数组

• 快速查询某个区间的和
  • 单点修改、区间查询
• lowbit(x)：x & (-x)，非负二进制整数x的最低位的1及其后面的0所构成的数。
• add和query：

  def add(i,k):
      if i <= 0: return
      n=len(nums)
      while i <= n:
          nums[i] += k
          i += lowbit(i)
  def query(i):
      res=0
      while i > 0:
          res += nums[i]
          i -= lowbit(i)
      return res

• 离散化树状数组
  • 计算右侧小于当前元素的个数

线段树

Trie树

Trie树（前缀树）用于高效地存储和检索字符串数据集中的键。
实现方式：数组、映射

并查集

• 查找

  def find(x):
      # 查找
      px=x
      while px != parent[x]:
          px = parent[x]
      
      # 路径压缩
      while x != px:
          temp=parent[x]
          parent[x]=px
          x=temp

• 合并

  def union(x,y):
      px=find(x)
      py=find(y)
      if px != py:
          if rank[px] > rank[py]:
              parent[py]=px
          elif rank[px] < rank[py]:
              parent[px]=py
          else:
              parent[py]=px
              rank[px]+=1

平衡二叉树

平衡二叉树首先是二叉排序树

树链剖分

二维/动态开点线段树

拓展

• 可持久化数据结构
• 树套树
• 动态树