这题珂朵莉是不是比块链优)
查看原帖
这题珂朵莉是不是比块链优)
147670
金珂拉楼主2021/9/2 17:53

块链split操作的时候要暴力split,复杂度为块长,对块长最大值也有要求。

而链表式珂朵莉(或者说是数组映射优化的块链?)每一块只是一个l、r和几个tag(表示这段数字来源于是原数组、INSERT操作、Reverse的情况以及区间覆盖的情况),所以对于块内可以直接用代数方法O(1/Olog)split,对块长最大值无要求,块数最大值为相邻两次重构之间的操作次数的两倍。

而这题显然数字总数以及插入总数比块数大,所以定期重构的珂朵莉似乎更优?

(不过珂朵莉树重构的时候需要牵扯到数字总数,好像也差不多?)

2021/9/2 17:53
加载中...