zcmimi's blog

categories/算法/数据结构/共8篇文章

avatar
zcmimi
2020-04-14 10:26:00

简介

k-D Tree(KDT,k-Dimension Tree)是一种可以高效处理k维空间信息的数据结构。

维基百科

在算法竞赛的题目中,一般k=2

构建

`

avatar
zcmimi
2020-03-29 16:58:00

link-cut tree是一个挺复杂的东西,本文主要用于复习巩固link-cut tree

推荐:

#

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

比如要合并集合A,B,设|A|<|B|

这时候将 向B中插入A 的效率要比 向A插入B

这就是启发式合并的思想

Q: 很简单,但有什么用?

A: 假设我们要合并n个元素

avatar
zcmimi
2020-02-01

Dynamic Rankings为例:

如果不带修改,那就是普通的主席树

待修改: 树状数组套动态开点权值线段树

对于修改a_p,

受影响的有[p,n]

但是我们不需要从p修改到n

可以

前置知识: 莫队算法(Mo's Algorithm)

树上莫队:

也就是把莫队搬到树上

入手模板: SP10707 COT2 - Count on a tree II

给定一个n个节点的树,每个

avatar
zcmimi
2019-01-20 00:23:01

二维线段树一般用线段树套线段树写,当然也可以用四叉树

树套树,顾名思义,外层树的每个节点都是一棵树。

[题目地址:https://www.luogu.org/problemnew/

avatar
zcmimi
2018-12-29 22:31:53

学习的原因:

之所以选择fhqtreap,不是因为可以可持久化,是因为:

1. 短

2. 好理解、好记

3. 应用范围广

不过学之前还是先对treap原理稍微有些了解比较好

其中有些细节还是要靠自己意会意会

原理:

概述:

f

avatar
zcmimi
2018-12-01 21:10:58

https://www.luogu.org/problemnew/show/P3369

最短(最简洁)代码:

解释:
turn(x,p):
    将x的左(p=0)/右(p=1)儿子旋转到x的头顶(变成x的父亲)

![](https://i.loli.net/2018/12/05/

1/1
Search
search