Дан массив в 10^9 элементов, но известно, что одновременно в нем может храниться не более 10^6 (скажем, ненулевые, остальные нули). Элементы могут как добавляться, так и удаляться. Способ хранения с возможностью только добавления я придумал — время доступа O( (log(n))^3 ). А вот с удалением проблемы. Кто-нибудь знает, где можно найти алгоритм и структуру данных? Должны быть относительно быстрыми операции вставки, удаления, присваивания, взятия значения и поиск.