SPOJ 375 - Query on a tree[QTREE]

张文泰 posted @ 2010年4月08日 00:56 in Art of Science with tags SPOJ 数据结构 , 4899 阅读

这个题目相当经典了,是一个树结构的询问题。一般而言,这种题目都是先给出一个树,然后进行更改边权值、对边的修改(节点也可以),然后对某段路径进行询问。从根本上来讲,这类题目的本质都是在维护树的路径。

QTREE算是这类题目中的一道入门题。给出一棵树,然后更改边的权值或者询问一条路径上边权最大的边。由于不涉及树的形态,我们直接用树链剖分先构造固定的线段树来维护路径。对于相应的更改和询问,只要先预处理好LCA就可以轻松维护了。

在树中不同路径中遍历的复杂度是O(log n),查询一次边的复杂度是O(log n),每次查询LCA的复杂度是O(log n)。我在预处理LCA的时候采用的是O(n log n)-O(log n)的算法,所以总的复杂度就是O(n log n+q log2 n)。事实上,如果我们用RMQ的O(n)-O(1)算法来处理这个LCA,复杂度就应该是O(n+qlog2 n)。

值得注意的是,使用gets()优化一下输入,程序会快很多,我的程序就快了1.37s。至于为什么我的程序这么慢,只能说明我的代码写得太烂了。

Your program in C++ from 2010-04-07 07:19:34 ran for 4.09 seconds and used 4424 KB of memory.

Your program in C++ from 2010-04-07 11:05:42 ran for 2.72 seconds and used 4348 KB of memory.


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter