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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

几种线段树写法的时间差异

Posted by zoanthropy at 2020-07-30 18:39:46 on Problem 1151
翻了一下自己以前写的代码,看着感觉好像不大对劲,然后发现了问题
网上题解的线段树有大致三种写法
一是边界范围判在t[x].l+1==t[x].r的地方的
  如https://www.cnblogs.com/flyawayl/p/8868211.html
二是边界判在t[x].l>=left&&t[x].r<=right,且有pushdown的
  如https://blog.csdn.net/riba2534/article/details/76851233
三是边界判断同二,但是没有pushdown的
  如https://www.jianshu.com/p/d70f6d346913
第一种写法将每一个长度为n的修改区间都分为到n*logn个节点处理,这种写法时间复杂度为O(n^2logn),其实比n方暴力还慢,本人代码实测16ms
第二种是常规写法,不过比第三种常数大,都是O(nlogn),实测都为0ms
第三种写法是利用需要的数据都在根节点的性质,所有节点的数据都是单向往父节点传,同时无需更改,因此父节点数据不用传向子节点,可以省略pushdown(但写法不同),可见李煜东《算进》p220
  

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