Минимальное значение между двумя элементами последовательности

Question

Я пытаюсь создать программу, которая сохранит последовательность чисел в массиве в времени O (N), чтобы быстро ответить (O (logn)) на следующее.

min (int i, int j): возвращает значение минимального значения в последовательности между значениями i и j.

например, если последовательность A = (22, 51, 83, 42, 90, 102, 114, 35), и я называю min (3,6) , она вернется 4, поскольку 42 < 83,90,102.

Я понимаю, что невозможно достичь быстрого времени, если значения последовательности не отсортированы и потому, что я хочу достичь O (logn), я думал о реализации двоичного дерева.

Проблема в том, что я не могу понять, каким образом я должен поместить значения последовательности в двоичном дереве для быстрого доступа к ним, чтобы min() работал так, как мне нужно.

Answer 1

Это типичная проблема, которую нужно решить с помощью дерева интервалов. Вы можете построить его в O(n) времени, а затем запустить запросы в O(log n).

Общая идея состоит в том, чтобы иметь идеальное двоичное дерево, хранящееся в массиве, где узел с индексом i имеет своих детей по индексам 2i и 2i+1. В листьях вы сохраняете значения вашей последовательности, и для каждого нелистового узла вы храните минимум всех своих потомков. Если вы построите дерево из листьев вверх, вы можете сделать это в O(n) времени.

Чтобы выполнить запрос для интервала [a; b], вы можете взять два основных подхода (как работа в O(log n) время):

• , идущие к корню из листьев a и b
• рекурсивно идущих в направлении вниз дерево, начинающееся с корня

Описание обоих методов, которые вы можете легко найти в Интернете под фразой «интервал дерева». Для вашей проблемы я определенно рекомендую первый, потому что это должно быть немного быстрее.

В соответствии с просьбой я распространил свой ответ с инструкциями по запросу дерева. Давайте поближе рассмотрим подход «снизу вверх», который я предложил для вашей проблемы. Я собираюсь предположить, что массив индексируется от 0 до n - 1. Я также предполагаю, что n равен 2^k для некоторых натуральных k. Если нет, вы увеличите его до ближайшей мощности 2, добавив +Inf элементов в конце нижнего уровня в случае запроса минимального значения. Это не повлияет на какой-либо действительный запрос, и вы получите идеальное двоичное дерево, которое можно легко проиндексировать, как я описал ранее. Для удобной реализации я предлагаю использовать индекс 1 для корня, и это также предполагается для этого описания.

Этот рисунок должен сделать вещи более ясными. Черные индексы внизу - это индексы из исходного массива. Зелеными индексами рядом с каждым узлом являются индексы в дереве. Пока игнорируем прямоугольники, поскольку они относятся к примеру запроса.

По query(a, b) мы будем обозначать запрос для минимума в интервале [a; b] (включительно).Во-первых, частный случай: когда a равен b, мы просто возвращаем tree[n + a] (учтите, что это правильный индекс, когда tree[1] является корнем).

Перейдем к более сложному случаю, когда a != b. Подсказка алгоритма состоит в том, что мы можем разбить любой интервал на базовые интервалы O(log n), которые не имеют общих элементов и полностью покрывают исходный интервал. Размер каждого базового интервала равен мощности 2, и каждый базовый интервал представлен одним из наших узлов. Когда мы перечислим все соответствующие интервалы, нам нужно взять минимум их узлов, чтобы получить ответ за query(a, b).

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

int x = a + n; 
int y = b + n; 
int result = Math.min(tree[x], tree[y]); 

while (x/2 != y/2) { 
    if (x % 2 == 0) { 
     result = Math.min(result, tree[x + 1]); 
    } 
    if (y % 2 == 1) { 
     result = Math.min(result, tree[y - 1]); 
    } 

    x /= 2; 
    y /= 2; 
} 

Сначала преобразовать исходные показатели в индексы в дереве. Затем мы учитываем интервалы с одним элементом, содержащие границы вашего запроса. Помните, что я исключил специальный случай, когда a == b.

Алгоритм выполняется следующим образом, перемещаясь вверх по дереву. Всякий раз, когда x % 2 == 0 учитываем интервал, который является братом, равным x в дереве. Пожалуйста, убедитесь, что этот брат всегда полностью содержится в интервале [a; b]. То же самое мы делаем для y % 2 == 1, за исключением того, что брат находится слева от y. Когда x/2 == y/2 это означает, что x и y теперь являются братьями и сестрами, и мы должны остановить алгоритм. Вы можете сами убедиться, что этот подход выбирает интервалы в том, как они полностью покрывают [a; b].

Обратите внимание, что мы можем проверить не более 4 узлов в нижнем уровне дерева. На уровне друг друга мы будем проверять не более двух узлов. Поскольку есть O(log n) уровней дерева, мы можем видеть, что временная сложность любого запроса равна O(log n).

Бонус - изменение массива. Проблема, о которой вы описали, не требует модификации массива, но в базовом случае она настолько чиста, что я собираюсь добавить ее здесь. Если вы также хотели бы обработать команду set(a, v), то есть array[a] = v, вы можете легко сделать это в O(log n) раз. Сначала вы устанавливаете tree[a + n] = v, а затем отправляетесь к корню, обновляя минимумы на своем пути.