Skip to content

Limstash的博客

  • 首页
  • 图床
  • 关于我

树结构

[题解] ZJOI2019 线段树

2019年4月13日2020年8月3日 Wong, LimstashOI, 线段树

题目描述 九条可怜是一个喜欢数据结构的女孩子,在常见的数据结构中,可怜最喜欢的就 […]

Read more

[题解] HAOI2012 高速公路

2019年4月8日2020年8月3日 Wong, LimstashOI, 数学, 数学期望, 线段树

题目描述 Y901 高速公路是一条重要的交通纽带,政府部门建设初期的投入以及使用 […]

Read more

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

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

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

Read more

[题解] NOI2018 归程(Kruskal重构树)

2019年2月17日2020年8月3日 Wong, LimstashKruskal重构树, OI

Kruskal 重构树是一种基于 Kruskal 算法,在求解最小生成树的同时建出一棵新树。Kruskal 重构树是一个二叉堆,原图两点之间边权最大值等于 Kruskal 重构树上 LCA 权值

Read more

[模板] 替罪羊树与Treap

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

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

Read more

[模板] 可持久化线段树 & 主席树

2018年12月9日2020年8月3日 Wong, LimstashOI, 可持久化线段树, 树结构

可持久化线段树是一种能支持访问历史版本的线段树,能实现基于某一个历史版本的操作。主席树和可持久化线段树一般是等价的,但更多时候主席树一般是一棵权值(值域)线段树

Read more

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

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

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

Read more

[题解] Luogu – 3398 仓鼠找sugar

2018年10月11日2020年8月3日 Wong, LimstashOI, 倍增, 最近公共祖先

题目描述 小仓鼠的和他的基(mei)友(zi)sugar 住在地下洞穴中,每个节 […]

Read more

[题解] Luogu 1631 – 序列合并

2018年10月11日2020年8月3日 Wong, LimstashOI, 堆, 树结构

题目描述 有两个长度都是 $N$ 的序列 $A$ 和 $B$ ,在 $A$ 和 […]

Read more

[模板] 权值线段树

2018年9月10日2020年8月3日 Wong, LimstashOI, 权值线段树

权值线段树较普通线段树不同地方在于:权值线段树的数组范围 $n$ 是它的值域大小 […]

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.