- •Структуры данных
- •Insert (X) – добавляет в очередь новый объект X;
- •Init (n) – инициализировать систему непересекающихся множеств, поместив в нее набор из n непересекающихся множеств – по одному множеству для каждого объекта.
- •Init (n) – заполнить таблицу a[1..N] нулями.
- •Init (n) – установить значения в таблице a[1..N], равными бесконечности.
- •Init (n);
- •Init (n) – инициализирует систему (все парковочные места свободны);
- •Init (c);
- •Init (c);
Init (n) – заполнить таблицу a[1..N] нулями.
Упражнение 11. Предложите (идейно) простую реализацию сумматора, в которой операция MODIFY выполняется за O(1), а операция FINDSUM – за O(Sqrt(N)).
Перейдем теперь к реализации сумматора. Нам понадобятся некоторые дополнительные обозначения. Рассмотрим произвольное натуральное число X. Переведем его в двоичную запись: X = (akak-1…a0)2. Будем идти по этой записи справа налево, пока не встретим единицу. Пусть это будет at. Таким образом, at = 1 и ai = 0 для i < t. Пусть теперь NEXT (x) – это число, равное X + 2t (мы также будем говорить, что NEXT (x) получается из x добавлением крайнего справа бита), а PREV (x) – это число, равное X - 2t (мы будем говорить, что PREV (x) получается из x удалением крайнего справа бита). Величины NEXT (x) и PREV (x) будут очень важными во всех наших структурах данных, поэтому мы хотим уметь вычислять их быстро – за O(1). Ниже приведен один из вариантов такого вычисления.
Function PREV (x)
Return x and (x-1)
End;
Function NEXT (x)
Return (x shl 1) – (x and (x-1))
End;
Упражнение 12. Покажите, что приведенные алгоритмы корректно вычисляют значения NEXT (x) и PREV (x).
Как ни странно, в нашей реализации сумматора значения элементов таблицы A храниться не будут. Вместо этого мы будем использовать таблицу S[1..N]. Смысл элемента S[i] таков: S[i] равен сумме элементов таблицы A в интервале индексов от PREV (i) + 1 до i, то есть S[i] = A[PREV (i) + 1] + A[PREV (i) + 2] + … + A[i-1] + A[i]. В частности, если i – нечетно, то S[i] = A[i]. Операция INIT, как обычно, тривиальна. Время ее работы составляет O(N).
Operation INIT (N)
For i:= 1 to N Do
S[i]:= 0;
End;
Разберемся теперь, как выполнять операцию FINDSUM. Сначала мы рассмотрим частный случай, когда l = 1. Идея состоит в следующем. Рассмотрим значение S[r] – в нем хранится сумма ячеек от (Prev(r)+1) – ой до r – ой. Если разделить отрезок от 1 до r на две части: от 1 до PREV (r) и от PREV (r) + 1 до r, то получаем, что сумма значений на отрезке от 1 до r равна FINDSUM (1, PREV (r)) + S[r]. Таким образом, в данном случае мы можем воспользоваться рекурсией. Пусть теперь l > 1. Тогда для нахождения суммы значений на отрезке от l до r можно использовать то, что эта сумма равна разности FINDSUM (1, r) – FINDSUM (1, l-1), а случай l = 1 мы уже рассмотрели. Таким образом, получаем следующую реализацию операции FINDSUM.
Operation FINDSUM (l, r)
If l > 1
Then Return FINDSUM (1, r) – FINDSUM (1, l-1)
Else
If r > 0
Then Return FINDSUM (1, PREV (r)) + S[r]
Else Return 0;
End;
Не проводя пока временного анализа, перепишем операцию FINDSUM в более понятном нерекурсивном виде.
Operation FINDSUM (l, r)
Sum:= 0;
x:= r;
While x > 0 Do Begin
Sum:= Sum + S[x];
x:= PREV (x);
End;
x:= l-1;
While x > 0 Do Begin
Sum:= Sum – S[x];
x:= PREV (x);
End;
Return Sum;
End;
Время работы операции теперь оценить несложно. Во время работы каждого из циклов While у переменной x на каждой итерации количество единиц в двоичной записи уменьшается на 1. Так как перед каждым из циклов ее значение было не больше N, то и количество единиц в ее двоичной записи не превосходило O(logN). Итак, общее время работы операции FINDSUM есть O(logN).
Нам осталось только описать, как реализовать операцию MODIFY. Общая идея тут такова: нужно найти все такие x, что позиция pos лежит на отрезке [PREV (x) + 1, x] и изменить значения S[x] на value. Следующая теорема описывает все числа x, обладающие нужным нам свойством.
Теорема 3. Все числа x такие, что pos лежит на отрезке [PREV (x) + 1, x] можно построить следующим образом: x0 = pos; xk = NEXT (xk-1), k ≥ 1.
Доказательство. Понятно, что x0 – минимальное число, обладающее нужным нам свойством. Далее заметим следующее, пусть pos лежит на отрезке [PREV (xk) + 1, xk] и крайний справа бит в двоичной записи xk находится на позиции. Если рассмотреть произвольное x из отрезка [xk+1, NEXT (xk) –1], то у числа x крайний справа бит будет находиться на позиции, меньшей t, а значит PREV (x) ≥ xk. Так как pos ≤ xk, то pos не может находиться на отрезке [PREV (x) +1, x]. С другой стороны, если рассмотреть xk+1 = NEXT (xk), то нетрудно видеть, что PREV (xk+1) ≤ PREV (xk) и поэтому pos будет находиться на отрезке [PREV (xk+1) +1, xk+1]. Таким образом, xk+1 – минимальное число, большее xk, обладающее нужным нам свойством. ٱ
Основываясь на доказанной теореме, нетрудно написать реализацию операции MODIFY.
Operation MODIFY (pos, value)
x:= pos;
While x <= N Do Begin
S[x]:= S[x]+value;
x:= NEXT (x);
End;
End;
Временной анализ операции MODIFY также несложен. В цикле While позиция крайнего справа бита в числе x на каждой итерации увеличивается. Следовательно, через O(logN) операций x гарантированно станет больше, чем N. Таким образом, время работы операции MODIFY составляет O(logN).
Упражнение 13. Предположим, что в таблице A находятся некоторые числа, которые не меняются и необходимо эффективно выполнять в ней операцию FINDSUM. Предложите простой способ для выполнения этой операции за O(1). Вам разрешается провести предварительную подготовку к выполнению запросов FINDSUM (например, вычислить какую-нибудь дополнительную информацию). Время на предварительную подготовку не должно превышать O(N).
б) Минимизатор. Под минимизатором будем понимать структуру данных, выполняющую две операции:
MODIFY (pos, value) – установить значение A[pos] равным min{A[pos], value}.
FINDMIN (l, r) – найти минимальное из значений в таблице с индексами от l до r, то есть min{A[l], A[l+1], …, A[r-1], A[r]}.
Сюда опять же добавляется инициализация таблицы: