~ Esoteria Algorithm in Reverse Observatory

FHQ Treap | 非旋式树堆

Prologue

前置技能

一些定义

  • 树中任意节点的权值都大于或等于其父节点的权值,则称该二叉树满足 “小根堆性质”
  • 二元搜寻树(Binary Search Tree, BST)是一棵空树或具有下列性质的二叉树

左偏树

Prologue

左偏树是一种合并复杂度很优秀的堆。下图就是一棵典型的左偏树,蓝色的数字为该节点的路径长。

分块

Prologue

  • 块:将一个数列分为若干个不相交区间,每一个区间称为块
  • 完整块:进行区间操作时被区间完全覆盖的块
  • 不完整块:进行区间操作时部分被区间覆盖的块

线段树

Introduction Chapter

有一类问题,数据通常可以建模到数轴或是数列上,操作一般是每次对数轴上的一个区间或是数列中的连续若干个数进行修改、查询等,数据规模往往比较大。这些数据就适合用线段树维护。