Эффективный поиск пола и потолка каждого элемента после вставки в массив

Question

Предположим, что массив имеет элементы [1,n]. Существует непрерывный ввод элементов (m запросов) один за другим. Как ниже.

1. 5, поэтому вы должны напечатать 1 как floor и 10 как ceil, тогда массив станет [1,5,10]
2. 2, поэтому выведите 1 как floor, а 5 как ceil и array: [1,2,5,10]

как это дано m запросов. Этаж и потолок и могут быть найдены с O (log n) сложностью времени, поскольку мы поддерживаем отсортированный массив.

Но проблема в том, что позиция элемента для вставки составляет O(log n), а вставка - O(n) для перемещения других чисел в худшем случае, что приводит к O(log n) + O(n) для каждого запроса.

Так что для m запросов в худшем случае это будет mxO(logn + n), что слишком дорого. Я хочу, чтобы эти операции выполнялись менее чем за mxO(logn + n).

Answer 1

Вместо массива вы должны использовать сбалансированное двоичное дерево поиска.Вставка и нижние / верхние границы (то есть «floor» и «ceil») выполняются в O(log n), что дает общее время выполнения O(m log m).

. Вы не упомянули язык, но какНапример, с использованием контейнера C ++ set (который реализует двоичное дерево поиска) код будет выглядеть следующим образом:

std::set<int> A;
A.insert(1);
A.insert(n);

for(int i = 0; i < m; ++i) {
    int x;
    scanf("%d", &x);
    assert(1 < x && x < n);
    auto iter = A.insert(x).first;
    printf("floor: %d, ceil: %d\n", *prev(iter), *next(iter));
}