Можно сделать все операции за O(1). Для этого берем Purely Functional, Real-Time Deques with Catenation (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451) и храним в каждом элементе структуры минимум (на самом деле, это должно работать с любым моноидом).
Если достаточно амортизированного O(1), то выкидываем идею про recursive slow-down (вместе с расскраской и счетчиками) -- и получаем, фактически, rope (http://en.wikipedia.org/wiki/Rope_(data_structure)) на основе леса полных деревьев.
no subject
Date: 2014-03-24 05:43 pm (UTC)Если достаточно амортизированного O(1), то выкидываем идею про recursive slow-down (вместе с расскраской и счетчиками) -- и получаем, фактически, rope (http://en.wikipedia.org/wiki/Rope_(data_structure)) на основе леса полных деревьев.