线段树的合并与分裂

线段树的合并

如果要实现线段树的合并,那么线段树必须是动态开点的。否则,想想都不对吧。。。

通过上面这份代码,便可以实现动态开点的线段树的合并。

时间复杂度也是可以保证的。

假如把原树中的NULL点也看成一个点,那么每调用一次merge函数,就会有一个点作废,因此调用merge的次数是O(原点数)的,因此时间复杂度可以保证。

线段树的分裂

动态开点的线段树也是可以分裂的。

每次调用split会使点数最多增加 O(lgn)

线段树的合并与分裂
Tagged on:     

2 thoughts on “线段树的合并与分裂

发表评论

电子邮件地址不会被公开。 必填项已用*标注