анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 9 Запросы по диапазону В этой главе мы обсудим структуры данных для эффективной обработки запросов к массивам по диапазону. Типичные примеры таких запросов: вычисление суммы по диапазону и нахождение минимума по диапазону. В разделе 9.1 рассматривается простая ситуация, когда массив не мо- дифицируется между запросами. В таком случае достаточно подвергнуть массив предварительной обработке, чтобы можно было эффективно най- ти ответ на любой возможный запрос. Сначала мы научимся обрабатывать запросы о сумме с помощью массива префиксных сумм, а затем обсудим алгоритм разреженной таблицы для обработки запросов о минимуме. В разделе 9.2 представлены две древовидные структуры, позволяющие эффективно обрабатывать запросы и изменять значения элементов мас- сива. Двоичное индексное дерево поддерживает запросы о сумме и может рассматриваться как динамический вариант массива префиксных сумм. Дерево отрезков – более универсальная структура, поддерживающая за- просы о сумме, запросы о минимуме и некоторые другие. Все операции над обеими структурами имеют логарифмическую сложность. 9.1. Запросы к статическим массивам В этом разделе мы рассмотрим ситуацию, когда массив статический, т. е. не изменяется между запросами. Тогда достаточно подвергнуть его пред- варительной обработке с целью эффективного получения ответов на за- просы по диапазону. Сначала обсудим простой способ обработки запросов о сумме с помощью массива префиксных сумм, который допускает обобщение на многомер- ный случай. Затем изучим несколько более сложный алгоритм разрежен- ной таблицы для обработки запросов о минимуме. Запросы о максимуме обрабатываются аналогично. 9.1.1. Запросы о сумме Обозначим sum q (a, b)(«запрос о сумме по диапазону») сумму элементов массива в диапазоне [a, b]. Любой запрос о сумме можно эффективно об- работать, если сначала построить массив префиксных сумм. Каждый эле- 9.1. Запросы к статическим массивам 145 мент этого массива равен сумме нескольких первых элементов исходного массива, т. е. значение k-го элемента равно sum q (0, k). На рис. 9.1 показаны массив и соответствующий ему массив префиксных сумм. 1 3 4 8 6 1 4 2 0 1 2 3 4 5 6 7 original array 1 4 8 16 22 23 27 29 0 1 2 3 4 5 6 7 prefix sum array Исходный массив Массив префиксных сумм Рис. 9.1. Массив и соответствующий ему массив префиксных сумм Массив префиксных сумм можно построить за время O(n). Поскольку он содержит значения sum q (0, k) для всех k, то любое значение вида sum q (a, b) можно вычислить за время O(1)по формуле sum q (a, b) = sum q (0, b) – sum q (0, a – 1). Положив sum q (0,–1) = 0, мы распространим эту формулу и на случай a = 0. На рис. 9.2 показано, как вычисляется сумма по диапазону [3, 6] с по- мощью массива префиксных сумм. Легко вычислить, что sum q (3, 6) = 8 + 6 + 1 + 4 = 19. Пользуясь же массивом префиксных сумм, мы можем обойтись всего двумя значениями: sum q (3, 6) = sum q (0, 6) − sum q (0, 2) = 27 − 8 = 19. 1 3 4 8 6 1 4 2 0 1 2 3 4 5 6 7 original array 1 4 8 16 22 23 27 29 0 1 2 3 4 5 6 7 prefix sum array Исходный массив Массив префиксных сумм Рис. 9.2. Вычисление запроса о сумме по диапазону с помощью массива префиксных сумм Многомерный случай. Эта идея обобщается и на многомерный случай. На рис. 9.3 показан двумерный массив префиксных сумм, который можно использовать для вычисления суммы по любому прямоугольному подмас- сиву за время O(1). Каждая сумма в этом массиве соответствует подмасси- ву, начинающемуся в левом верхнем углу массива. Сумму по серому под- массиву можно вычислить по формуле S(A) − S(B) − S(C) + S(D), где S(X)– сумма элементов прямоугольного подмассива, занимающего ле- вый верхний угол исходного массива вплоть до позиции X. 146 Глава 9. Запросы по диапазону A B C D Рис. 9.3. Вычисление суммы по диапазону в двумерном случае 9.1.2. Запросы о минимуме Обозначим min q (a, b)(«запрос о минимуме по диапазону») минималь- ный элемент массива в диапазоне [a, b]. Мы рассмотрим метод, позволя- ющий обработать запрос о минимуме по диапазону за время O(1)после предварительной обработки, занимающей время O(n log n). Этот метод, предложенный в работе Bender, Farach-Colton [3], часто называют алго- ритмом разреженной таблицы. Идея заключается в том, чтобы заранее вычислить min q (a, b)для случаев, когда b – a + 1 (длина диапазона) является степенью двойки. На рис. 9.4 показаны предвычисленные значения для массива из 8 элементов. 1 3 4 8 6 1 4 2 0 1 2 3 4 5 6 7 original array 1 3 4 6 1 1 2 – 0 1 2 3 4 5 6 7 range size 2 1 3 1 1 1 – – – 0 1 2 3 4 5 6 7 range size 4 1 – – – – – – – 0 1 2 3 4 5 6 7 range size 8 Размер диапазона 2 Размер диапазона 4 Размер диапазона 8 Исходный массив Рис. 9.4. Предварительная обработка для запросов о минимуме Количество предвычисляемых значений имеет порядок O(n log n), по- скольку существует O(log n) длин диапазонов, являющихся степенью двой- ки. Эти значения можно эффективно вычислить по рекуррентной формуле min q (a, b) = min( min q (a, a + w − 1), min q (a + w, b)), где b − a + 1 – степень двойки, а w = (b − a + 1)/2. Вычисление всех значений занимает время O(n log n). 9.2. Древовидные структуры 147 После этого любое значение min q (a, b)можно вычислить за время O(1), взяв минимум двух предвычисленных значений. Пусть k – наибольшая степень двойки, не превосходящая b − a + 1. Значение min q (a, b) вычисля- ется по формуле min q (a, b) = min( min q (a, a + k − 1), min q (b − k + 1, b)). В этой формуле диапазон [a, b] представлен как объединение двух диа- пазонов длины k: [a, a + k − 1] и [b − k + 1, b]. Для примера рассмотрим диапазон [1,6] на рис. 9.5. Его длина равна 6, а максимальная степень двойки, не превосходящая 6, – это 4. Таким об- разом, диапазон [1,6] является объединением диапазонов [1,4] и [3,6]. Поскольку min q (1, 4)= 3 и min q (3,6)= 1, можно заключить, что min q (1, 6) = 1. 1 3 4 8 6 1 4 2 0 1 2 3 4 5 6 7 range size 6 1 3 4 8 6 1 4 2 0 1 2 3 4 5 6 7 range size 4 1 3 4 8 6 1 4 2 0 1 2 3 4 5 6 7 range size 4 Размер диапазона 6 Размер диапазона 4 Размер диапазона 4 Рис. 9.5. Вычисление минимума по диапазону с помощью двух перекрывающихся диапазонов Отметим, что с помощью довольно сложных методов можно обработать запрос о минимуме по диапазону за время O(1)после предобработки, за- нимающей лишь время O(n)(см., например, Fischer, Heun [12]), но эти ме- тоды выходят за рамки книги. 9.2. Древовидные структуры В этом разделе мы представим две древовидные структуры, позволяющие обрабатывать запросы по диапазону и изменять значения элементов мас- сива за логарифмическое время. Сначала обсудим двоичные индексные деревья, поддерживающие запросы о сумме, а затем – деревья отрезков, поддерживающие также запросы других видов. 9.2.1. Двоичные индексные деревья Двоичное индексное дерево (или дерево Фенвика) [11] можно рассматри- вать как динамический вариант массива префиксных сумм. Оно предо- ставляет две операции с временной сложностью O(log n): обработка за- проса о сумме по диапазону и изменение значения. Хотя в названии этой 148 Глава 9. Запросы по диапазону структуры данных фигурирует слово «дерево», обычно она представляется в виде массива. При обсуждении двоичных индексных деревьев мы будем предполагать, что все массивы индексируются, начиная с 1, потому что это упрощает реализацию структуры. Обозначим p(k)наибольшую степень двойки, делящую k. Двоичное ин- дексное дерево хранится в массиве tree таким образом, что tree [ k] = sum q (k − p(k) + 1, k), т. е. элемент в позиции k содержит сумму по заканчивающемуся в этой позиции диапазону длины p(k). Например, поскольку p(6) = 2, tree [6] со- держит значение sum q (5, 6). На рис. 9.6 показаны массив и соответствующее ему двоичное индексное дерево. На рис. 9.7 показано соответствие между значениями двоичного индексного дерева и диапазонами исходного мас- сива. 1 3 4 8 6 1 4 2 1 2 3 4 5 6 7 8 original array 1 4 4 16 6 7 4 29 1 2 3 4 5 6 7 8 binary indexed tree Исходный массив Двоичное индекcное дерево Рис. 9.6. Массив и его двоичное индекcное дерево 1 4 4 16 6 7 4 29 1 2 3 4 5 6 7 8 Рис. 9.7. Соответствие между двоичным индексным деревом и диапазонами Зная двоичное индексное дерево, мы можем вычислить любое значение вида sum q (1, k)за время O(log n), поскольку диапазон [1, k] всегда можно разбить на O(log n)поддиапазонов, суммы по которым хранятся в дере- ве. Например, чтобы вычислить sum q (1, 7), мы разобьем диапазон [1, 7] на три поддиапазона: [1, 4], [5, 6] и [7, 7] (рис. 9.8). Поскольку суммы по этим поддиапазонам уже имеются в дереве, то мы можем вычислить сумму по всему диапазону по формуле: sum q (1, 7) = sum q (1, 4) + sum q (5, 6) + sum q (7, 7) = 16 + 7 + 4 = 27. 9.2. Древовидные структуры 149 1 4 4 16 6 7 4 29 1 2 3 4 5 6 7 8 Рис. 9.8. Обработка запроса о сумме по диапазону с помощью двоичного индексного дерева А чтобы вычислить значение sum q (a, b), где a > 1, мы применим тот же прием, что в случае массивов префиксных сумм: sum q (a, b) = sum q (1, b) − sum q (1, a − 1). И sum q (1, b), и sum q (1, a − 1)можно вычислить за время O(log n), поэтому полная временная сложность равна O(log n). После изменения любого элемента массива необходимо обновить дво- ичное индексное дерево. Например, если изменяется элемент 3, то следует обновить суммы по диапазонам [3, 3], [1, 4] и [1, 8] (рис. 9.9). Поскольку каждый элемент массива принадлежит O(log n)такимдиапазонам, то до- статочно обновить O(log n) элементов дерева. 1 4 4 16 6 7 4 29 1 2 3 4 5 6 7 8 Рис. 9.9. Обновление значения в двоичном индексном дереве Реализация. Операции двоичного индексного дерева эффективно реа- лизуются с помощью поразрядных операций. Нам понадобится следую щий факт: значение p(k)можно вычислить по формуле: p(k) = k & −k, которая выделяет самый младший единичный бит k. Следующая функция вычисляет sum q (1, k): int sum(int k) { int s = 0; 150 Глава 9. Запросы по диапазону while (k >= 1) { s += tree[k]; k -= k&-k; } return s; } А эта функция увеличивает значение k-го элемента массивана x (x мо- жет иметь любой знак): void add(int k, int x) { while (k <= n) { tree[k] += x; k += k&-k; } } Временная сложность обеих функций равна O(log n), потому что они об- ращаются к O(log n)элементам двоичного индексного дерева, а переход к следующей позиции занимает время O(1). 9.2.2. Деревья отрезков Дерево отрезков – это структура данных, предоставляющая две опера- ции с временной сложностью O(log n): обработка запроса по диапазону и изменение элемента массива. Деревья отрезков поддерживают запросы о сумме, о минимуме и многие другие. Своими корнями деревья отрез- ков уходят в геометрические алгоритмы (см., например, Bentley, Wood [4]), а элегантная восходящая реализация, представленная в этом разделе, взя- та из книги Stańczyk [34]. Дерево отрезков – это двоичное дерево, в котором вершины нижнего уровня соответствуют элементам массива, а остальные несут информа- цию, необходимую для выполнения запросов по диапазону. При обсужде- нии деревьев отрезков мы будем предполагать, что размер массива – сте- пень двойки, и использовать индексирование, начиная с нуля, потому что для такого массива строить дерево отрезков удобнее. Если размер массива не является степенью двойки, то всегда можно добавить в конец элементы. Сначала обсудим деревья отрезков, поддерживающие запросы о сум- ме. На рис. 9.10 показаны массив и соответствующее ему дерево отрезков. Каждая внутренняя вершина дерева соответствует некоторому диапазо- ну массива, размер которого равен степени двойки. Для дерева отрезков, поддерживающего запросы о сумме, значение в каждой внутренней вер- шине равно сумме элементов соответствующего диапазона, и его можно вычислить как сумму значений в левой и правой дочерних вершинах. 9.2. Древовидные структуры 151 5 8 6 3 2 7 2 6 0 1 2 3 4 5 6 7 5 8 6 3 2 7 2 6 13 9 9 8 22 17 39 Рис. 9.10. Массив и соответствующее ему дерево отрезков для запросов о суммах Оказывается, что любой диапазон [a, b] можно разбить на O(log n)под- диапазонов, таких, что суммы их элементов уже хранятся в дереве от- резков. На рис. 9.11 показан диапазон [2, 7] в исходном массиве и в де- реве отрезков. В данном случае диапазону соответствуют две вершины и sum q (2, 7) = 9 + 17 = 26. Если при вычислении этой суммы используются вершины, расположенные как можно выше, то понадобится не более двух вершин на каждом уровне дерева. Поэтому общее число участвующих в вычислении вершин имеет порядок O(log n). 5 8 6 3 2 7 2 6 0 1 2 3 4 5 6 7 5 8 6 3 2 7 2 6 13 9 9 8 22 17 39 Рис. 9.11. Обработка запроса о сумме по диапазону с помощью дерева отрезков После изменения некоторого элемента массива необходимо обновить все вершины, значения в которых зависят от измененного элемента. Для 152 Глава 9. Запросы по диапазону этого следует пройти по пути от измененного элемента к корню дерева, обновляя все встретившиеся вершины. На рис. 9.12 показано, какие вер- шины обновляются после изменения пятого элемента. Путь от листа де- рева к корню содержит O(log n)вершин, поэтому при любом изменении обновляется O(log n)вершин. 5 8 6 3 2 7 2 6 0 1 2 3 4 5 6 7 5 8 6 3 2 7 2 6 13 9 9 8 22 17 39 Рис. 9.12. Как изменение элемента массива отражается на дереве отрезков Реализация. Хранить дерево отрезков удобно в массиве из 2n элемен- тов, где n – размер исходного массива. Вершины хранятся сверху вниз: tree [1] – корень, tree [2] и tree [3] – его дочерние вершины и т. д. Наконец, элементы tree [n ] по tree [2 n − 1] соответствуют нижнему уровню дерева, на котором находятся элементы исходного массива. Отметим, что элемент tree [0] не используется. На рис. 9.13 показано, как хранится дерево, изображенное на рис. 9.11. Отметим, что родителем элемента tree [ k] является tree [ ⌊k/2⌋], его левым потомком – tree [2 k], а правым потомком – tree [2 k + 1]. Кроме того, любая вершина (кроме корня) занимает четную позицию, если это левый пото- мок своего родителя, и нечетную – если правый. 39 22 17 13 9 9 8 5 8 6 3 2 7 2 6 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Рис. 9.13. Хранение дерева отрезков в виде массива Следующая функция вычисляет значение sum q (a, b): int sum(int a, int b) { a += n; b += n; int s = 0; 9.2. Древовидные структуры 153 while (a <= b) { if (a%2 == 1) s += tree[a++]; if (b%2 == 0) s += tree[b--]; a /= 2; b /= 2; } return s; } Функция работает с диапазоном в массиве, представляющем дерево от- резков. Первоначально это диапазон [a + n, b + n]. На каждой итерации цикла диапазон поднимается на один уровень дерева выше, и значения в вершинах, не принадлежащих расположенному выше диапазону, прибав- ляются к сумме. Следующая функция увеличивает k-й элемент массива на x: void add(int k, int x) { k += n; tree[k] += x; for (k /= 2; k >= 1; k /= 2) { tree[k] = tree[2*k]+tree[2*k+1]; } } Сначала обновляется значение на нижнем уровне, а затем – значения всех внутренних вершин дерева на пути до корня. Обе функции работают за время O(log n), поскольку дерево отрезков для массива с n элементами содержит O(log n)уровней, а та и другая функции на каждой итерации поднимаются на один уровень выше. Другие запросы. Деревья отрезков способны поддержать и другие за- просы по диапазону, при условии что диапазон можно разбить на две по- ловины, вычислить ответ для каждой части и эффективно объединить оба ответа. Примером может служить нахождение минимума и максимума, наибольшего общего делителя, а также поразрядные операции И, ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ. Так, дерево отрезков на рис. 9.14 поддерживает запросы о минимуме. В нем каждая вершина содержит наименьшее значение в соответствую- щем диапазоне массива. В корне дерева находится минимум по всему мас- сиву. Операции можно реализовать так же, как и выше, но вместо сумм вычисляются минимумы. Структура дерева отрезков также позволяет использовать для нахождения элементов массива метод двоичного поис- ка. Например, если дерево поддерживает запросы о минимуме, то можно найти позицию элемента с наименьшим значением за время O(log n). На рис. 9.15 показано, как элемент с наименьшим значением 1 ищется путем спуска по дереву, начиная с корня. 154 Глава 9. Запросы по диапазону 5 8 6 3 1 7 2 6 5 3 1 2 3 1 1 5 8 6 3 1 7 2 6 5 3 1 2 3 1 1 Рис. 9.14. Дерево отрезков для обработки запросов о минимуме по диапазону Рис. 9.15. Использование дво- ичного поиска для нахождения минимального элемента 9.2.3. Дополнительные приемы Сжатие координат. В структурах данных, основанных на массивах, эле- менты индексируются последовательными целыми числами – и это мож- но считать ограничением. Трудности возникают, когда нужны большие индексы. Например, если требуется использовать индекс 10 9 , то массив должен содержать 10 9 элементов, для чего нужно слишком много памяти. Но если все индексы, которые могут понадобиться алгоритму, извест- ны заранее, то это ограничение можно обойти, воспользовавшись сжати- ем координат. Идея заключается в том, чтобы заменить исходные числа после довательными целыми числами 0, 1, 2 и т. д. Для этого мы опреде- лим функцию сжатия координат c. Она сопоставляет каждому исходному индексу i сжатый индекс c(i)таким образом, что если a и b – два числа и a < b, то c(a) < c(b). Сжатые индексы удобно использовать для выполнения запросов по диапазону. На рис. 9.16 приведен пример сжатия координат. Здесь реально исполь- зуются только индексы 2, 5 и 7, а все остальные элементы массива равны нулю. В результате сжатия остаются индексы c(2)= 0, c(5)= 1, c(7)= 2, что позволяет создать сжатый массив всего из трех элементов. 0 0 5 0 0 3 0 4 0 1 2 3 4 5 6 7 original array 5 3 4 0 1 2 compressed array Исходный массив Сжатый массив Рис. 9.16. Сжатие массива с помощью сжатия индексов После сжатия координат мы можем, к примеру, построить дерево от- резков для сжатого массива и выполнять запросы. Нужно будет внести 9.2. Древовидные структуры 155 только одну модификацию – сжимать координаты перед выполнением запроса: диа пазону [a, b] исходного массива соответствует диапазон [c(a), c(b)] сжатого. Обновление диапазона. До сих пор мы рассматривали структуры дан- ных, которые поддерживают запросы по диапазону и изменение одного значения. Теперь обратимся к противоположной ситуации: требуется об- новить диапазон и извлечь одно значение. Рассмотрим операцию увели- чения всех элементов в диапазоне [a, b] на x. Оказывается, что представленные в этой главе структуры данных мож- но использовать и для такой цели. Для этого построим разностный массив, в котором будут храниться разности между соседними элементами ис- ходного массива. Тогда исходный массив является массивом префиксных сумм для разностного. На рис. 9.17 показаны массив и соответствующий ему разностный массив. Так, значению 2 в шестой позиции исходного мас- сива соответствует сумма 3 − 2 + 4 − 3 = 2 в разностном массиве. 3 3 1 1 1 5 2 2 0 1 2 3 4 5 6 7 original array 3 0 −2 0 0 4 −3 0 0 1 2 3 4 5 6 7 difference array Исходный массив Разностный массив Рис. 9.17. Массив и соответствующий ему разностный массив У разностного массива имеется полезное свойство: чтобы изменить диа пазон исходного массива, достаточно изменить всего два элемента разностного. Точнее, чтобы увеличить все элементы в диапазоне [a, b] на x , достаточно увеличить элемент разностного массива в позиции a на x и уменьшить элемент в позиции b + 1 на x. Например, чтобы увеличить все элементы исходного массива с первого по четвертый на 3, мы прибавим 3 к первому элементу разностного массива и вычтем 3 из пятого элемента (рис. 9.18). 3 6 4 4 4 5 2 2 0 1 2 3 4 5 6 7 original array 3 3 −2 0 0 1 −3 0 0 1 2 3 4 5 6 7 difference array Исходный массив Разностный массив Рис. 9.18. Обновление диапазона массива с помощью разностного массива Таким образом, мы изменяем только отдельные значения в разностном массиве и выполняем для него запросы о сумме, следовательно, можно 156 Глава 9. Запросы по диапазону воспользоваться двоичным индексным деревом или деревом отрезков. Более трудная задача – придумать структуру данных, которая поддер- живала бы одновременно запросы по диапазону и обновления диапазона. В разделе 15.2.1 мы увидим, что это можно сделать с помощью ленивого дерева отрезков. |