首页 > 其他分享 >KDT学习笔记

KDT学习笔记

时间：2023-09-03 16:24:52浏览次数：42  
标签：p2 Node p0 p1 const int 笔记 学习 KDT

这次稍微水了点。

todo：

  • 复杂度。
  • 不知道是否存在的二进制分组优化。

偏序问题

一般是 CDQ，常数小；或者可持久化，拿来做区间问题；万能的树套树，就是吃空间。

然后就是 KDT，多位偏序无脑叠，空间线性，时间……玄学。

有时也有更好的方法，比如用 std::bitset 优化偏序，不过量有限，而且我不会。

KDT

用于快速检索 k维信息。

做法类似二叉搜索树，把中位数放在中间再分左右子树，但是比较按不同维度轮着来，选维度可以按顺序或者取方差最大（划分更均匀）。

注意的是检索时，因为一次划分只确定一维，所以需要把整棵树遍历一遍，但是当然要去掉无用部分以及可以剪枝。

像二位数点的领域查询，可以最优性剪掉部分子树；矩阵查询把包含和无交剪掉，就是 \(\mathcal{O}(\sqrt{n})\) 的。

时间复杂度有保证的，一般就是 k维矩阵 查询，结论是最坏 \(\mathcal{O}(n^{1-\frac{1}{k}})\) 的，证明咕。

大概介绍完，谈一下实现。

图方便，下面这颗 KDT 是 Leafy 的（类线段树结构），实现的是矩阵查询。

粗略实现

先考虑离线建树，只需像线段树一样操作即可，注意维护子树上的矩阵信息（最值、和）。

注意要按当前维度划分，使用 std::nth_element 可以把元素放在指定的位置，这样建树的复杂度是 \(\mathcal{O}(n\lg n)\) 的。

具体用法是：std::nth_element(p+l,p+mid,p+r+1,cmp)，按照 cmp 排序后的 p 数组内第 mid 个元素会被放在 p[mid] 处，其他部分不定顺序。

查询无脑递归两边，遇到不合法的就剪枝。

大概有这样一颗支持建树、查询、清空、剪枝的 KDT：

template<int K,int N,typename _Val,typename _Tp,template<int,typename,typename> class _Cut>//最后这坨是模板模板参，不建议学……
class KDTree_base{
//Point 和 Node 都是用数组存的
protected:
	static _Cut<K,_Val,_Tp> cuter;
	Point<K,_Val,_Tp> *point;
	Node<K,_Val,_Tp> tr[N<<2];
	void pull(int p){
		for(int k=0;k<K;++k) tr[p].L[k]=std::min(tr[p<<1].L[k],tr[p<<1|1].L[k]);
		for(int k=0;k<K;++k) tr[p].R[k]=std::max(tr[p<<1].R[k],tr[p<<1|1].R[k]);
		for(int k=0;k<K;++k) tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	}
	template<int k>
	void build(int p,int l,int r){
		if(l==r) return tr[p]=point[l],void();
		int mid=(l+r)>>1;
		std::nth_element(point+l,point+mid,point+r+1,cmp<k,K,_Val,_Tp>);
		build<turn<k,K>>(p<<1,l,mid),build<turn<k,K>>(p<<1|1,mid+1,r);
		pull(p);
	}
	void query(int p,Node<K,_Val,_Tp> &it){
		if(invalid(it,tr[p])||cuter.cut(tr[p],it)) return;//不合法
		if(contain(it,tr[p])) return it.sum+=tr[p].sum,void();//完全包含
		query(p<<1,it),query(p<<1|1,it);
	}
	void clear(int p,int l,int r){
		tr[p]=Node<K,_Val,_Tp>();
		if(l>=r) return;
		int mid=(l+r)>>1;
		clear(p<<1,l,mid),clear(p<<1|1,mid+1,r);
	}
public:
	KDTree_base(Point<K,_Val,_Tp> *_point):point{_point}{}
	void clear(int l,int r){clear(1,l,r);}
	void build(int l,int r){build<0>(1,l,r);}
	void query(Node<K,_Val,_Tp> &it){query(1,it);}
};
template<int K,int N,typename _Val,typename _Tp,template<int,typename,typename> class _Cut>
_Cut<K,_Val,_Tp> KDTree_base<K,N,_Val,_Tp,_Cut>::cuter;

插入

比较麻烦，因为插入多了不能做到划分均匀。

可以学替罪羊树，暴力重构，但是树高不能完全保证（见参考），会影响时间复杂度。

还可以学耗儿树，根号分治，不过是把插入存起来暴力查询。

具体的，设一个上限 \(B\)，插入 \(B\) 个数后重构整棵树，取 \(B=\sqrt{n\lg n}\) 可得复杂度 \(\mathcal{O}(n\sqrt{n\lg n})\)，然后我没写过。

cmd 大佬介绍了另一种：开两颗 KDT,\(\sqrt{n}\) 个插入时并入小的，\(B\) 个插入时并入大的。

说法是 \(B=n^{\frac{3}{4}}\) 时取得重构复杂度为 \(\mathcal{O}(n^{\frac{5}{4}}\lg n)\)。

复杂度这块大概知道就行，我没算。

注意可以根据数据特征调大小。

用上一颗 KDT 实现的插入版本：

template<int K,int N,typename _Val=int,typename _Tp=int,template<int,typename,typename> class _Cut=None_Cut>
class KDTree{
protected:
	Point<K,_Val,_Tp> p[N];
	KDTree_base<K,N,_Val,_Tp,_Cut> T0;
	KDTree_base<K,int(ceil(pow(N,0.75))),_Val,_Tp,_Cut> T1;
	int p0,p1,p2;
public:
	KDTree():T0(p),T1(p),p0{},p1{},p2{}{}
	void clear(){
		T0.clear(1,p0),T1.clear(p0+1,p1);
		p0=p1=p2=0;
	}
	void insert(const std::initializer_list<_Tp> &d,_Val v){
		++p2;
		int k=0;
		for(auto it:d) p[p2].d[k++]=it;
		p[p2].v=v;
		if(1ll*(p2-p1)*(p2-p1)>p2*1.25) T1.build(p0+1,p1=p2);
		else if(p1-p0>1.2*pow(p2,0.75)) T0.build(1,p0=p1),T1.build(p0+1,p1=p2);
	}
	_Val query(const std::initializer_list<_Tp> &L,const std::initializer_list<_Tp> &R){
		Node<K,_Val,_Tp> qry={};
		int k=0;
		for(auto it:L) qry.L[k++]=it;
		k=0;
		for(auto it:R) qry.R[k++]=it;
		T0.query(qry),T1.query(qry);
		for(int i=p1+1;i<=p2;++i)
			if(contain(qry,Node<K,_Val,_Tp>(p[i]))) qry.sum+=p[i].v;
		return qry.sum;
	}
};

一道题

万恶之源。

15s 的时限，在 QOJ 上暴力乱杀，HDU 正解 TLE……

不会写四毛子也不想被卡常，所幸这个题也算是个矩阵查询的多维偏序。

所以把求和改成最值，套板子就行了。

注意当心清空：

//不剪枝 15s 跑满，剪完只跑了 7s。
#include<cstdio>
#include<algorithm>
#define memcpy __builtin_memcpy
#define pow __builtin_pow
#define ceil __builtin_ceil
namespace KD_Tree{
	template<int K,typename _Val,typename _Tp>
	struct Point{
		_Tp d[K];
		_Val v;
	};
	template<int k,int K,typename _Val,typename _Tp>
	static bool cmp(const Point<K,_Val,_Tp> &x,const Point<K,_Val,_Tp> &y){return x.d[k]<y.d[k];}
	template<int K,typename _Val,typename _Tp>
	struct Node{
		_Tp L[K],R[K];
		_Val sum;
		Node():L{},R{},sum{}{}
		Node(const Point<K,_Val,_Tp> &p):sum{p.v}{memcpy(L,p.d,sizeof L),memcpy(R,p.d,sizeof R);}
	};
	template<int K,typename _Val,typename _Tp>
	bool contain(const Node<K,_Val,_Tp> &p,const Node<K,_Val,_Tp> &q){
		for(int k=0;k<K;++k) if(!(p.L[k]<=q.L[k]&&q.R[k]<=p.R[k])) return false;
		return true;
	}
	template<int K,typename _Val,typename _Tp>
	bool invalid(const Node<K,_Val,_Tp> &p,const Node<K,_Val,_Tp> &q){
		for(int k=0;k<K;++k) if(q.L[k]>p.R[k]||q.R[k]<p.L[k]) return true;
		return false;
	}
	template<int K,typename _Val,typename _Tp>
	struct None_Cut{bool cut(const Node<K,_Val,_Tp> &p,const Node<K,_Val,_Tp> &qry)const{return false;}};
	template<int k,int K>
	static constexpr int turn=k+1==K?0:k+1;
	template<int K,int N,typename _Val,typename _Tp,template<int,typename,typename> class _Cut>
	class KDTree_base{
	protected:
		static _Cut<K,_Val,_Tp> cuter;
		Point<K,_Val,_Tp> *point;
		Node<K,_Val,_Tp> tr[N<<2];
		void pull(int p){
			for(int k=0;k<K;++k) tr[p].L[k]=std::min(tr[p<<1].L[k],tr[p<<1|1].L[k]);
			for(int k=0;k<K;++k) tr[p].R[k]=std::max(tr[p<<1].R[k],tr[p<<1|1].R[k]);
			for(int k=0;k<K;++k) tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
		}
		template<int k>
		void build(int p,int l,int r){
			if(l==r) return tr[p]=point[l],void();
			int mid=(l+r)>>1;
			std::nth_element(point+l,point+mid,point+r+1,cmp<k,K,_Val,_Tp>);
			build<turn<k,K>>(p<<1,l,mid),build<turn<k,K>>(p<<1|1,mid+1,r);
			pull(p);
		}
		void query(int p,Node<K,_Val,_Tp> &it){
			if(invalid(it,tr[p])||cuter.cut(tr[p],it)) return;
			if(contain(it,tr[p])) return it.sum+=tr[p].sum,void();
			query(p<<1,it),query(p<<1|1,it);
		}
		void clear(int p,int l,int r){
			tr[p]=Node<K,_Val,_Tp>();
			if(l>=r) return;
			int mid=(l+r)>>1;
			clear(p<<1,l,mid),clear(p<<1|1,mid+1,r);
		}
	public:
		KDTree_base(Point<K,_Val,_Tp> *_point):point{_point}{}
		void clear(int l,int r){clear(1,l,r);}
		void build(int l,int r){build<0>(1,l,r);}
		void query(Node<K,_Val,_Tp> &it){query(1,it);}
	};
	template<int K,int N,typename _Val,typename _Tp,template<int,typename,typename> class _Cut>
	_Cut<K,_Val,_Tp> KDTree_base<K,N,_Val,_Tp,_Cut>::cuter;
	template<int K,int N,typename _Val=int,typename _Tp=int,template<int,typename,typename> class _Cut=None_Cut>
	class KDTree{
	protected:
		Point<K,_Val,_Tp> p[N];
		KDTree_base<K,N,_Val,_Tp,_Cut> T0;
		KDTree_base<K,int(ceil(pow(N,0.75))),_Val,_Tp,_Cut> T1;
		int p0,p1,p2;
	public:
		KDTree():T0(p),T1(p),p0{},p1{},p2{}{}
		void clear(){
			T0.clear(1,p0),T1.clear(p0+1,p1);
			p0=p1=p2=0;
		}
		void insert(const std::initializer_list<_Tp> &d,_Val v){
			++p2;
			int k=0;
			for(auto it:d) p[p2].d[k++]=it;
			p[p2].v=v;
			if(1ll*(p2-p1)*(p2-p1)>p2*1.25) T1.build(p0+1,p1=p2);
			else if(p1-p0>1.2*pow(p2,0.75)) T0.build(1,p0=p1),T1.build(p0+1,p1=p2);
		}
		_Val query(const std::initializer_list<_Tp> &L,const std::initializer_list<_Tp> &R){
			Node<K,_Val,_Tp> qry={};
			int k=0;
			for(auto it:L) qry.L[k++]=it;
			k=0;
			for(auto it:R) qry.R[k++]=it;
			T0.query(qry),T1.query(qry);
			for(int i=p1+1;i<=p2;++i)
				if(contain(qry,Node<K,_Val,_Tp>(p[i]))) qry.sum+=p[i].v;
			return qry.sum;
		}
	};
}
constexpr int N=5e4+5,Inf=0x3f3f3f3f;
struct Val{
	int v;
	Val():v{}{}
	Val(int _v):v{_v}{}
	Val operator+=(const Val &it){return v=std::max(v,it.v),*this;}
	Val operator+(const Val &it){return Val(std::max(v,it.v));}
};
template<int K,typename _Val,typename _Tp>
struct Cut{bool cut(const KD_Tree::Node<K,_Val,_Tp> &p,const KD_Tree::Node<K,_Val,_Tp> &qry)const{return p.sum.v<qry.sum.v;}};
KD_Tree::KDTree<5,N,Val,int,Cut> kdt;
int n;
Val dp[N];
void solve(){
	kdt.clear(),std::scanf("%d",&n);
	for(int k=1;k<=n;++k){
		int w,g,i,f,l,v;
		std::scanf("%d%d%d%d%d%d",&w,&g,&i,&f,&l,&v);
		dp[k].v=kdt.query({0,0,0,0,0},{w,g,i,f,l}).v+v;
		std::printf("%d\n",dp[k].v);
		kdt.insert({w,g,i,f,l},dp[k]);
	}
}
signed main(){
	int Test;
	std::scanf("%d",&Test);
	for(;Test--;) solve();
	return 0;
}

End

参考：

cmd 的博客（典中典）

OI-wiki（评论部分也很有价值）

标签：p2,Node,p0,p1,const,int,笔记,学习,KDT
From： https://www.cnblogs.com/LQ636721/p/17675087.html

相关文章

  • 02Java学习_注意事项和学习方法
    02_Java开发注意事项细节和学习方法注意事项.java是Java文件的拓展名。源文件的基本组成部分是类--class。Java程序的执行入口是main方法，固有的书写格式为：publicstaticvoidmain(String[]args){......}java语言严格区分大小写。Java方法由一条条语句......
  • *【学习笔记】(21) Prufer 序列
    Prufer序列Prufer序列可以将一个带标号\(n\)个节点的树用\([1,n]\)中的\(n-2\)个整数表示，即\(n\)个点的完全图的生成树与长度为\(n-2\)值域为\([1,n]\)的数列构成的双射。Prufer序列可以方便的解决一类树相关的计数问题，比如凯莱定理：\(n\)个点的完全图的生成树有......
  • Python学习第二天
    一、Python2or3?Insummary:Python2.xislegacy,Python3.xisthepresentandfutureofthelanguagePython3.0wasreleasedin2008.Thefinal2.xversion2.7releasecameoutinmid-2010,withastatementofextendedsupportforthisend-of-lifereleas......
  • 《C++并发编程实战》读书笔记(2)：线程间共享数据
    1、使用互斥量在C++中，我们通过构造std::mutex的实例来创建互斥量，调用成员函数lock()对其加锁，调用unlock()解锁。但通常更推荐的做法是使用标准库提供的类模板std::lock_guard<>，它针对互斥量实现了RAII手法：在构造时给互斥量加锁，析构时解锁。两个类都在头文件<mutex>里声明。std::......
  • 科普：人工智能与机器学习的关系
    大家好，我是炼数之道，一个在人工智能之路上学习和摸索的算法工程师。今天的文章在前期推文的基础上，继续用通俗的话来介绍人工智能领域的基本概念。前期文章回顾：《科普：什么是机器学习》、《科普：什么是深度学习？什么是人工智能？》 那么，人工智能和机器学习之间的关系是什么呢？下图很好......
  • celery笔记
    celery介绍1.它是什么？分布式的异步任务框架直译为:芹菜[/ˈseləri]2.可以做什么？异步任务。（异步执行函数）延迟任务。（延迟5s任务（函数））定时任务。（例如：每天23点触发测试）[如果单纯执行定时任务，没必要用celery]3.平台问题celeryisaprojectwithminimal......
  • python学习
    python学习正则表达式的使用正则表达式以下是替换指定文件夹下文本中的内容对图片形式的pdf提取目录，可以用以下程序叠加多个正则表达式来去除重复项。importosimportredefreplace_timestamp(directory):#遍历目录下的所有文件和文件夹forroot,dirs,fil......
  • openGauss学习笔记-59 openGauss 数据库管理-相关概念介绍
    openGauss学习笔记-59openGauss数据库管理-相关概念介绍59.1数据库数据库用于管理各类数据对象，与其他数据库隔离。创建数据对象时可以指定对应的表空间，如果不指定相应的表空间，相关的对象会默认保存在PG_DEFAULT空间中。数据库管理的对象可分布在多个表空间上。59.2表空间在......
  • 分布式服务的接口幂等性如何设计 笔记
    幂等:多次调用方法或者接口不会改变业务状态，可以保证重复调用的结果和单次调用的结果一致。需要幂等场景：用户重复点击(网络波动)MQ消息重复应用使用失败或超时重试机制1.数据库唯一索引(新增)不建议使用2.token+redis（新增、修改）3.分布式锁（新增、修改）快速失败（抢不到锁的线程）控制......
  • 多线程学习第四篇
    4、线程同步机制并发：同一对象被多个线程同时操作（抢票）线程同步是一个等待机制，多个需要同时访问次对象的线程进入这个对象的等待池形成队列，等待前一个线程使用完毕，下一个线程才能使用。形成线程安全的条件：队列和锁由于同一进程的多个线程共享同一块存储空间，在带来方便的同时，也......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99