上学期的新手赛和CSP被各路大佬吊打QwQ，在复习的时候发现还有KD树这个数据结构没有了解过，所以今天就让我们一起来学习多维查找树-KD树吧。PS不知不觉就第100篇BLOG了有点激动！！！ 什么是KD树 KD树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，x2，……，xk)）进行划分的一种数据结构，主要应用于索引结构中...
你还在为手写优先队列而头疼吗？你还在为hash写不出而烦恼吗？你已经想我一样成为板子都不想背的夕阳红选手了吗？非常好，现在，隆重向你推荐一批超级好用的STL函数。 队列-queue #include<queue>//queue头文件 #include<cstdio> #include<cstdlib> using namespace std; que...
什么，RMQ问题你还是只会线段树？什么，区间最值有1e7个查询，O(nlogn)卡不过去？没事，这篇BLOG，就让我们一同学习RMQ[区间最值]问题的另一个大杀器——ST表。 什么是ST表 ST表是一种神奇的数据结构，它虽说有它的短板——不支持修改，但它的特点同样很鲜明——短小精悍，能做到O(nlogn)的预处理，O(1)的单次查询，速度吊锤隔壁的线段树。别看名字很高级，其思路其实就是我...
在众多的线段树题目中，有一种题目一直占有一席之地，那就是染色问题，这篇BLOG，我们就针对染色问题，来浅谈一下这一类问题的解决方法 一维染色问题 这一类题目，一般都有一个固定的样式，当你对题目进行简化以后，总会得到类似与下面这种模型类似： 在一条数轴上，依次进行n次操作，每次操作读入3个数,x,y,z，表示在区间[x,y]中涂上颜色z，后涂上的颜色会覆盖之前涂上的颜色。问最后我们还能看...
我们在之前的BLOG已经多次提到了，平衡树的本质是BST(二叉查找树)，而平衡树的作用是为了加速二叉查找树，但不添加任何内容，可以说是BST的加速版。但是Splay却恰好相反，为了得到更多的功能，splay牺牲了时间和空间，其本质目的不是为了加速二叉排序树，而是为了增加一些普通二叉排序树所不具有的功能，所以splay可以称得上是BST的ex版，所以splay从本质目的上来说已经算不上是平衡...