Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:关于线段树开空间大小的问题

Posted by shenyang_ at 2011-09-06 09:51:03 on Problem 2828
In Reply To:Re:关于线段树开空间大小的问题 Posted by:allentest at 2010-09-08 17:15:36
> http://allenlsy.com/2010/09/08/poj-2828/
> 
> n*2的建树方法,适用于动态建树,就是说没有任何一个节点被浪费的建法。而这里我使用的,或者说大多数人使用的这种用x*2表示左子树 x*2+1表示右子树的建法,是不能只开到n*2的,因为有写节点没用到。
> 举个列子来说,假如线段树的n = 11,你认为应该建树为22或者23,保守点。
> (去网站看图)
> 如果你要找[9,9]的区间,就会出现RTE了。
> 那么开多少才正确呢?
> 其实,应该是 2^ ( seiling( log2(n) )+1 ), 即2的log2(n)的上取整加1次幂。
> 这道题目,用此方法计算,得到实际需要空间大小524288,我开了524300,AC了
一般开到4倍

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator