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

Question

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

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

Answer 1

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

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

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