SPOJ 375 - Query on a tree[QTREE]

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

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

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
TN 8th Model Paper 2 说:
2022年8月25日 22:04

Tamilnadu 8th Std Model Question Paper Tamilnadu 8th Standard Tamil Question Paper 2023, 6th Standard Model Question Paper Tamilnadu English Medium Kalvisolai 8th Model Question Paper With Answers 8th Standard Tamil Medium Model Question Paper Tamilnadu 8th Standard Question Paper 2023, TN 8th Model Paper 2023 Tamil Nadu STD 8th Class Model Paper 2023, and Sarva Shiksha Abhiyan State Level Achievement Survey 2023, Question Paper Subject wise STD-VIII, TN 8th Question Paper 2023, 8th Standard Model Question Paper 2023, 8th Standard Question Paper 2023.


登录 *


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