Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:有可能是空间用的少了时间也少一些.系统寻址要少很多..In Reply To:Re:怎么个直接计算法?? Posted by:411465294 at 2007-11-27 13:07:22 > 我的想法是 线段树 最下层的节点,不一定非要对应一个数。 > 可以是一个比较小的区间~~ > 如果 区间 长度为 2^n , (原来长度可认为是 1 ), 那么 线段树的层数将少n层。 > 即时假设, 区间长度取 2 , 那么 将少一层, 这在 空间上可是个不可忽视的节约~ > 然后是时间上: 由于按这种方法, 执行Q ,C 指令后, 会比原来少一个结点维护,同时系统也少开了个栈(而节点维护中,可能存在乘法运算), 而这样呢,付出的代价是:最多只比原来多 > 两次加法运算。 > 但是上面所说的 时间上的优势,只会发生在输入数据[a,b]两边 的小区域, 所以效率不会有很大的提高。但空间需求较少不少~。 > 还好,试过之后,事实的确如此~~ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator