Skip to content

Limstash的博客

  • 首页
  • 图床
  • 关于我

平衡树

[模板] FHQ Treap 与可持久化平衡树

2019年2月25日2020年8月3日 Wong, LimstashOI, Treap, 可持久化平衡树, 平衡树

$\mathrm{FHQ} \ \mathrm{Treap}$ 是一类基于 $\mathrm{Split}$ 和 $\mathrm{Merge}$ 操作的平衡树,不需要旋转的特性是可持久化平衡树的基础

Read more

[模板] 替罪羊树与Treap

2019年1月20日2020年8月3日 Wong, LimstashOI, Treap, 替罪羊树, 树结构

替罪羊树(重量平衡树)和 Treap (树堆)也是两种常用的平衡树,分别基于平衡因子和随机附加域来保证子树的平衡。

Read more

[模板] 二逼平衡树(线段树套Splay)

2018年11月27日2020年8月3日 Wong, LimstashOI, Splay, 树套树, 树结构, 线段树

一道线段树套平衡树的模板题,支持在区间中完成平衡树的相关功能,本题可以在 $O(log^2 n)$ 的时间内进行区间单点修改,查询某一个区间内的前驱,后继,排名,并通过二分的方法,在 $O(log^3 n)$ 的时间内查询区间 $k$ 小值。

Read more

[模板] Luogu3369 – 伸展树Splay

2018年4月19日2020年8月3日 Wong, LimstashOI, Splay

$Splay$ 是一种二叉排序树,因此满足二叉排序树的所有性质。支持在 $O(l […]

Read more

语言

  • 中文 (中国)
  • English

分类

友链

  • DOFY
  • eatrice
  • encodetalker
  • Kalorona
  • OIerC
  • withoutpower
  • XG_Zepto
  • 隐私政策
赣ICP备2021000211号-1
© 2017 - 2025 limstash All rights reserved
Powered by WordPress | Theme based on Astrid by aThemes.