KD-Tree 学习笔记

发布于 2019-01-31

K-D Tree,全名k-dimensional Tree,是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如 …


LCT 维护子树信息

发布于 2019-01-30

众所周知 LCT 可以用来维护动态树的点权信息,但是总有一些题目让你维护动态树上的子树信息或者是链信息,就在这里拿一道经典的题目讲 …


「BZOJ2002」「HNOI2010」弹飞绵羊

发布于 2019-01-29

题目描述 题目链接 某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏 …


点分治初探

发布于 2019-01-29

点分治是什么: 首先选取一个点将无根树转为有根树,再递归处理每一棵以根节点的儿子为根的子树。 这样得到的分治结构有何用处? 通俗地 …


树上启发式合并学习笔记

发布于 2019-01-29

首先什么是启发式算法?启发式算法是基于人类的经验和直观感觉,对一些算法的优化。 最简单的就是并查集的按秩合并,每次把小的合并到大的 …


「CF487E」Tourists

发布于 2019-01-23

题目链接 题目描述 给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经 …


点双连通分量 & 圆方树学习笔记

发布于 2019-01-21

点双连通分量 点双连通图:如果一个无向图上没有割点,那么该图为点双连通图。显然有一个性质是同一个点双连通图中任意两点至少存在两条不 …


最小树形图 / 朱刘算法

发布于 2019-01-20

前置定义 树形图:在一个有向图中,满足存在一个入度为 $0$ 的点,除了该点入读均为 $1$,且该图不存在环,那么称为树形图。 最 …