This paper describes the most efficient way to manage operations on groups of consecutive elements, or "blocks" of elements, within an ordered set. The goal is to improve existing solutions, by optimizing the average-case time complexity and getting rid of heavy multiplicative constants in the worst-case, without sacrificing space complexity. This is an high-impact operation in practical applications, and will be performed by introducing a new data structure called Wise Red-Black Tree, an augmented version of the Red-Black Tree.
翻译:本文描述了管理一组连续元素(或“块状”元素)在一组有顺序的一组元素(或“块状”元素)的操作的最有效方式。 目标是通过优化平均时间复杂性和在最坏的情况下消除大量重复的常数,同时不牺牲空间复杂性,改进现有解决方案。 这是一个在实际应用中影响很大的操作,并将通过引入名为“ 智慧红黑树”的新数据结构( 红黑树, 红黑树的强化版本) 来实施。