1 Тема от witua Отредактировано witua (2010-02-08 22:02:55)

  • witua
  • Участник
  • Неактивен
  • Откуда: Львов
  • Зарегистрирован: 2010-01-26
  • Сообщений: 13

Тема: Структара данных - 2

С помощью какой структуры данных можно выполнять следующие операции:
- удаление элемента;
- поиск последнего за индексом (в данном неупорядоченном массиве чисел) числа,
которое меньше X;

Благодарю.

P.S. не хуже чем за log N

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Структара данных - 2

Тут можно использовать дерево отрезков. Для начала, построим дерево отрезков на массиве, которое для каждой вершины хранит минимальное число из отрезка, соответствующего ей.
Если мы хотим удалить число - просто поставим на его место +бесконечность.
Чтобы обработать запрос второго типа, нужно посмотреть, если у правого сына текущей вершины минимум не превышает заданного числа, значит рекурсивно переходим к нему, иначе переходим к левому сыну.
Все запросы работают за O(logN).

3 Ответ от witua

  • witua
  • Участник
  • Неактивен
  • Откуда: Львов
  • Зарегистрирован: 2010-01-26
  • Сообщений: 13

Re: Структара данных - 2

Понятно, спасибо. А можно как-то отвечать на запрос количества чисел, менше X в массиве (где X<= 10^9) с помощью дерева отрезков? если нет то как можно такое сделать?

4 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: Структара данных - 2

Если вам нужно только это...
Тогда можно написать сжатие чисел,чтобы все числа были (X <= N).
Это делается с помощью сортировки всех чисел,и каждому числу даём свой номер,при этом сохраняется соотношение
(X <= Y) -> (newX <= newY).
А теперь просто пишем Сумматор (Фенвика),и всё.