zcmimi's blog

arrow_back数据结构共19篇文章

avatar
zcmimi
2020-09-02 07:35:00
avatar
zcmimi
2020-05-25 19:22:00

SPOJ的GSS系列是关于区间统计技巧的集合

非常适合锻炼码力

LG GSS1 | SPOJ GSS1

[LG GSS2](

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

推荐:

#

avatar
zcmimi
2020-03-25 17:13:00

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.com.cn/pro

avatar
zcmimi
2020-03-20 20:36:00

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线操作

先将每个询问拆成4个点查询

(1,1)(x,y)中点数为s(x,y).

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

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

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

这就是启发式合并的思想

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

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

avatar
zcmimi
2020-02-01

Dynamic Rankings为例:

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

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

对于修改a_p,

受影响的有[p,n]

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

可以

avatar
zcmimi
2020-01-30

换根树链剖分

loj #139.树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

avatar
zcmimi
2019-01-30

建树

tarjan求出双连通分量后把其中的点连向新建的节点

建成的新图(树)即为圆方树

**性质:可

1/2
Search
search