Как использовать деревья сегментов, чтобы найти два наименьших числа и одно максимальное число в диапазоне в несортированном массиве?

В настоящее время я использую дерево сегментов, чтобы узнать наименьшее и наибольшее число в диапазоне в несортированном массиве, сравнивая и сохраняя наименьший и наибольший подмассивы.

Однако я запутался в том, какую информацию нужно сохранить при поиске двух наименьших чисел и одного наибольшего числа в диапазоне в несортированном массиве.


arrays segment-tree
person user3243499    schedule 17.06.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

На самом деле это довольно просто,
вместо того, чтобы хранить минимальное и максимальное значения в диапазоне узла, вы можете хранить максимальное значение и массив/массив списка минимальных значений.

При объединении 2 узлов:

  1. Создайте новый массив/ArrayList,
  2. скопируйте в него оба дочерних массива
  3. Сортировать
  4. Удаляйте элементы сзади, пока не получите массив размером ‹= 2.
person Photon    schedule 13.03.2019