CDQ分治小结

xiaoxiao2021-02-28  94

CDQ分治特别之处:时间

CDQ分治分的是时间。 然而。 时间又怎么了。 我们可以知道:时间上,后面的时间不能为前面的时间做贡献(只要你不站在上帝视角) 所以当且仅当 i<j 时, ansiansj 所以CDQ分治主要是这样做

void CDQ(l,r) { int mid=(l+r)>>1;//(l+r)/2 CDQ(l,mid); CDQ(mid+1,r); Do something. }

其中,我们设CDQ的复杂度为 T(i) ,Do something的复杂度用 D(i) 代替。 有 T(i)=2T(i2)+D(i) D(i)=O(n) T(i)=2T(i2)+O(1)=O(n log2n) D(i)=O(n log2n) T(i)=2T(i2)+O(n)=O(n log22n) 题目示例:三维偏序

转载请注明原文地址: https://www.6miu.com/read-47180.html

最新回复(0)