анти. Guide to Competitive

• Название: Guide to Competitive
• Дата: 20.12.2022
• Размер: 2.39 Mb.
• Имя файла: анти.pdf
• Тип: Guide; #854732
• страница: 22 из 26

int sum(int a, int b) {
a += n; b += n;
int s = 0;
while (a <= b) {
if (a%2 == 1) s += tree[a++];
if (b%2 == 0) s += tree[b--];
a /= 2; b /= 2;
}
return s;
}
Но в деревьях отрезков с дополнительными возможностями часто бы- вает необходимо реализовывать операции, выполняемые сверху вниз, на- пример:
int sum(int a, int b, int k, int x, int y) {
if (b < x || a > y) return 0;
if (a <= x && y <= b) return tree[k];
int d = (x+y)/2;
return sum(a,b,2*k,x,d) + sum(a,b,2*k+1,d+1,y);
}

15.2. И снова о деревьях отрезков

287
С помощью этой функции мы можем вычислить сумму в диапазоне [a, b] следующим образом:
int s = sum(a,b,1,0,n-1);
Параметр k обозначает текущую позицию в дереве. Первоначально k
равно 1, поскольку начинаем мы с корня дерева. Диапазон [x, y] соответ- ствует k и вначале равен [0, n − 1]. Если при вычислении суммы [x, y] оказы- вается вне [a, b], то сумма равна 0, а если [x, y] целиком расположен внутри
[a
, b], то сумму можно обнаружить в дереве. Если же [x, y] расположен час- тично внутри [a, b], то поиск продолжается рекурсивно в левой и правой половинах [x, y]. Левой половиной является диапазон [x, d], а правой – диа- пазон [d + 1, y], где d = ⌊(x + y)/2⌋.
На рис. 15.9 показано, как продвигается поиск при вычислении значе- ния sum
q
(a, b). Серым цветом закрашены вершины, в которых рекурсия останавливается, поскольку сумму можно найти в дереве. При такой реа- лизации операция занимает время O(log n), потому что общее число посе- щенных вершин равно O(log n).
5 8
6 3
2 7
2 6
7 1
7 5
6 2
3 2
13 9
9 8
8 12 8
5 22 17 20 13 39 33 72
b a
Рис. 15.9. Обход дерева отрезков сверху вниз
15.2.1. Ленивое распространение
С помощью ленивого распространения мы можем построить дерево отрезков, которое будет поддерживать как запросы, так и обновления по диапазону за время O(log n). Идея в том, чтобы выполнять обновления и запросы сверху вниз, причем обновления производить лениво, чтобы они распространялись вниз по дереву, только когда это необходимо.
В вершинах ленивого дерева отрезков хранится информация двух ти- пов. Как и в обычном дереве отрезков, в каждой вершине хранятся сумма, минимальное значение и другие данные, относящиеся к соответствую-

288 
Глава 15. Дополнительные темы щему диапазону массива. Дополнительно в вершине может храниться ин- формация о ленивом обновлении, которое еще не было распространено на потомков. Ленивое дерево отрезков способно поддержать два типа обнов- ления диапазона: каждый элемент диапазона либо увеличивается на неко- торую величину, либо ему присваивается новое значение. Для реализации обеих операций используются схожие идеи, и можно даже построить де- рево, которое будет поддерживать обе операции.
Рассмотрим случай, когда наша цель – построить дерево отрезков, под- держивающее две операции: увеличение каждого элемента в диапазоне
[a
, b] на постоянную величину и вычисление суммы элементов [a, b]. Для этого будем хранить в каждой вершине два значения s/z, где s – сумма эле- ментов диапазона, а z – величина ленивого обновления, т. е. все элементы диапазона следует увеличить на z. На рис. 15.10 показан пример такого дерева, в котором z = 0 во всех вершинах, т. е. невыполненных ленивых обновлений нет.
5 8
6 3
2 7
2 6
7 1
7 5
6 2
3 2
13/0 9/0 9/0 8/0 8/0 12/0 8/0 5/0 22/0 17/0 20/0 13/0 39/0 33/0 72/0
Рис. 15.10. Ленивое дерево отрезков для обновления диапазонов и запросов к ним
Будем реализовывать операции с деревом сверху вниз. Чтобы увеличить элементы диапазона [a, b] на u, модифицируем вершины следующим об- разом: если диапазон [x, y] вершины расположен целиком внутри [a, b], то увеличиваем значение z в этой вершине на u и останавливаемся. Если [x, y] частично расположен внутри [a, b], то продолжаем рекурсивный обход де- рева и после этого вычисляем новое значение s в вершине. На рис. 15.11 показано дерево после увеличения элементов диапазона [a, b] на 2.
И при обновлении, и при выполнении запросов ленивое обновление распространяется вниз по мере спуска по дереву. Перед тем как обратить- ся к вершине, мы всегда проверяем, существует ли в ней ленивое обновле- ние. Если да, то мы изменяем хранящееся в ней значение s, распространя- ем обновление на дочерние вершины, после чего сбрасываем значение z.
На рис. 15.12 показано, как изменяется дерево при вычислении sum
q
(a, b).

15.2. И снова о деревьях отрезков

289
Прямоугольник содержит вершины, значения которых изменяются, когда ленивое обновление распространяется вниз.
5 8
6 3
2 9
2 6
7 1
7 5
6 2
3 2
13/0 9/0 11/0 8/2 8/0 12/0 8/2 5/0 22/0 23/0 20/2 17/0 45/0 45/0 90/0
b a
Рис. 15.11. Увеличение элементов диапазона [a, b] на 2 5
8 6
3 2
9 2
6 7
1 7
5 6
2 3
2 13/0 9/0 11/0 8/2 8/2 12/2 8/2 5/0 22/0 23/0 28/0 17/0 45/0 45/0 90/0
b a
Рис. 15.12. Вычисление суммы элементов диапазона [a, b]
Полиномиальные обновления. Мы можем обобщить показанное выше дерево отрезков, так чтобы можно было обновлять диапазоны, ис- пользуя полиномы вида
p(u) = t
k
u
k
+ t
k−1
u
k−1
+ … + t
0
В этом случае после обновления i-й элемент диапазона[a, b] принима- ет значение p(i − a). Например, прибавление полинома p(u)= u + 1 к [a, b] означает, что элемент в позиции a увеличивается на 1, элемент в позиции
a + 1 – на 2 и т. д.
Для поддержки полиномиальных обновлений каждой вершине сопо- ставляется k + 2 значений, где k – степень полинома. Значение s равно сум-

290 
Глава 15. Дополнительные темы ме элементов диапазона, а z
0
, z
1
, …, z
k
– коэффициенты полинома, описы- вающие отложенное обновление. Тогда сумма элементов диапазона [x, y] равна
1 1
1 0
0
)
(
,
y x
u
k
k
k
k
z u
z
u
z u
z
s
−
−
−
=
+
+
+
+
+
∑

а значение такой суммы можно эффективно вычислить, применяя фор- мулы суммирования. Например, член z
0
соответствует сумме z
0
(y − x + 1), а член z
1
u – сумме
z
1
(0 + 1 + ··· + y − x) = z
1
(y − x)(y − x + 1) .
2
При распространении обновления по дереву индексы p(u) изменяют- ся, поскольку в каждом диапазоне [x, y] значения вычисляются для u = 0,
1, …, y − x. Однако с этим легко справиться, потому что p'(u)= p(u + h)– по- лином той же степени, что и p(u). Например, если p(u)= t
2
u
2
+ t
1
u + t
0
, то
p'(u)= t
2
(u + h)
2
+ t
1
(u + h)+ t
0
= t
2
u
2
+ (2ht
2
+ t
1
)u + t
2
h
2
+ t
1
h + t
0
.
15.2.2. Динамические деревья
Обычное дерево является статическим, т. е. все вершины занимают фиксированное положение в массиве, представляющем дерево отрезков, и для размещения структуры требуется память фиксированного размера.
В динамическом дереве отрезков память выделяется только для вершин, к которым действительно производятся обращения в процессе работы алго- ритма. Это может заметно сэкономить память.
Вершины динамического дерева можно представить такой структурой:
struct node {
int value;
int x, y;
node *left, *right;
node(int v, int x, int y) : value(v), x(x), y(y) {}
};
Здесь value
– значение в вершине, [
x
,
y
] – соответствующий диапазон, а left и right
– указатели на левое и правое поддеревья. Вершины создают- ся следующим образом:
// создать вершину со значением 2 и диапазоном [0,7]
node *x = new node(2,0,7);
// изменить значение x->value = 5;

15.2. И снова о деревьях отрезков

291
Разреженные деревья отрезков. Динамическое дерево отрезков осо- бенно полезно, когда стоящий за ним массив разреженный, т. е. диапазон его индексов [0, n − 1] велик, но большинство элементов – нули. Если для хранения обычного дерева отрезков понадобилась бы память объемом
O(n), то для динамического – только объемом O(k log n), где k – число вы- полненных операций.
В динамическом дереве отрезков первоначально имеется только одна вершина [0, n − 1] с нулевым значением; это означает, что все элементы массива равны нулю. По мере обновления в дерево динамически добавля- ются новые вершины. Любой путь от корня к листу содержит O(log n)вер- шин, так что всякая операция с деревом добавляет не более O(log n)новых вершин. Следовательно, после k операций дерево будет содержать O(k log
n
)вершин. На рис. 15.13 показано разреженное дерево отрезков, для кото- рого n = 16, а элементы в позициях 3 и 10 модифицированы.
[0
,
15
]
[0
,
7
]
[0
,
3
]
[2
,
3
]
[3
,
3
]
[8
,
15
]
[8
,
11
]
[10
,
11
]
[10
,
10
]
Рис. 15.13. Разреженное дерево отрезков, в котором элементы в позициях 3 и 10 модифицированы
Отметим, что если заранее известны все элементы, которые будут моди- фицированы в процессе работы алгоритма, то использовать динамическое дерево отрезков необязательно, т. к. можно обойтись обычным деревом отрезков со сжатием индексов (раздел 9.2.3). Однако это не получится, если индексы порождаются в ходе работы алгоритма.
Персистентные деревья отрезков. Динамическая реализация позво- ляет также создать персистентное дерево отрезков, в котором хранится
история модификации. Имея такую реализацию, мы можем эффективно обращаться ко всем версиям дерева, существовавшим за время выполне- ния алгоритма. Если доступна история модификации, то запросы к любой предыдущей версии дерева можно выполнять как к обычному дереву от- резков, поскольку сохранена полная структура каждого дерева. Мы также

292 
Глава 15. Дополнительные темы можем создавать новые деревья на базе предыдущих и модифицировать их независимо.
Рассмотрим последовательность обновлений на рис. 15.14, где помечен- ные вершины изменяются, а все остальные – нет. После каждого обновле- ния большинство вершин остаются неизменными, поэтому компактный способ хранения истории модификации заключается в том, чтобы пред- ставить каждую историческую версию дерева в виде комбинации новых вершин и поддеревьев предыдущих деревьев. На рис. 15.15 показано, как можно сохранить историю. Структуру каждого предыдущего дерева мож- но воссоздать, следуя по указателям, начиная с соответствующего корня.
Поскольку при каждой операции в дерево добавляется только O(log n)но- вых вершин, мы можем сохранить полную историю модификации дерева.
Шаг 1
Шаг 2
Шаг 3
Рис. 15.14. История модификации дерева отрезков: начальное дерево и два обновления
Шаг 3
Шаг 1
Шаг 2
Рис. 15.15. Способ компактного хранения истории модификаций
15.2.3. Структуры данных в вершинах
В вершинах дерева отрезков можно хранить не только одиночные зна- чения, но и целые структуры данных, содержащие информацию о соот- ветствующих диапазонах. Предположим, к примеру, что требуется эффек- тивно подсчитывать количество вхождений элемента x в диапазон [a, b].
Для этого можно создать дерево отрезков, каждой вершине которого со- поставлена структура данных, поддерживающая запросы о количестве вхождений в соответствующий ей диапазон. Тогда для вычисления ответа на запрос можно комбинировать результаты, полученные от вершин, при- надлежащих диапазону.

15.2. И снова о деревьях отрезков

293
Остается выбрать отвечающую задаче структуру данных. Вполне подой- дет отображение map
, в котором ключом является элемент массива, а зна- чением – число его вхождений в диапазон. На рис. 15.16 показаны массив и соответствующее ему дерево отрезков. Корень дерева говорит, что эле- мент 1 встречается в массиве 4 раза.
3 1
2 3
1 1
1 2
3 1
1 1
2 1
3 1
1 1
1 1
1 1
2 1
1 3 1 1 2 3 1 1 1
2 1 2 1 1 1 2 3 1 1 2 1 2 3 1 1 2 3 4 2 2
Рис. 15.16. Дерево отрезков для вычисления количества вхождений элемента в диапазон массива
Для выполнения каждого запроса с помощью этого дерева отрезков тре- буется время O(log
2
n), поскольку в каждой вершине хранится структура map
, операции с которой имеют временную сложность O(log n). Дерево по- требляет память объема O(n log n), т. к. состоит из O(log n)уровней, и на каж дом уровне находится n элементов, распределенных по структурам map
15.2.4. Двумерные деревья
Двумерное дерево отрезков позволяет обрабатывать запросы, относя- щиеся к прямоугольным подмассивам двумерного массива. Идея заклю- чается в том, чтобы создать дерево отрезков, соответствующее столбцам массива, а затем сопоставить каждой его вершине дерево сегментов, соот- ветствующее строкам массива.
На рис. 15.17 показано двумерное дерево отрезков, поддерживающее запросы двух видов: вычисление суммы элементов подмассива и обнов- ление одного элемента массива. Оба запроса занимают время O(log
2
n), поскольку производится обращение к O(log n)вершин основного дерева отрезков, а обработка каждой вершины занимает время O(log n). Структу- ра потребляет память объема O(n
2
), потому что основное дерево отрезков

294 
Глава 15. Дополнительные темы содержит O(n)вершин, и в каждой вершине хранится дерево с O(n)верши- нами.
7 6
1 6
8 7
5 2
3 9
7 1
8 5
3 8
7 6
1 6
13 7
20 8
7 5
2 15 7
22 3
9 7
1 12 8
20 8
5 3
8 13 11 24 15 13 6 8
28 14 42 11 14 10 9 25 19 44 26 27 16 17 53 33 86
Рис. 15.17. Двумерный массив и соответствующее дерево отрезков для вычисления суммы прямоугольных подмассивов
15.3. Дучи
Дуча (treap)– это двоичное дерево, в котором содержимое массива хранится таким образом, что массив можно эф- фективно разбить на два других, а два массива объединить в один. В каждой вершине дучи хранятся две величины:
вес
2
и значение. Вес вершины не превос- ходит веса любой из ее дочерних вер- шин, а в массиве любая вершина рас- положена после всех вершин ее левого поддерева и до всех вершин ее правого поддерева.
На рис. 15.18 приведен пример мас- сива и соответствующей ему дучи.
В частности, корневая вершина имеет
2
В русскоязычном сообществе эта величина носит название «приоритет». − Прим. ред.
S
A
N
D
W
I
C
H
0 1
2 3
4 5
6 7
9
S
3
A
6
N
1
D
8
W
9
I
4
C
5
H
Рис. 15.18. Массив и соответствующая ему дуча

15.3. Дучи

295
вес 1 и значение D. Левое поддерево содержит три вершины, поэтому эле- мент массива в позиции 3 имеет значение D.
15.3.1. Разбиение и слияние
При добавлении в дучу новой вершины ей приписывается случайный вес. Из-за этого дерево с высокой вероятностью будет сбалансированным
(высота равна O(log n)), и операции с ним выполняются эффективно.
Разбиение. Операция разбиения создает из одной дучи две, в результа- те чего массив разбивается на два таким образом, что первые k элементов принадлежат первому массиву, а остальные – второму. Для этого мы создаем две новые, первоначально пустые дучи и обходим исходную дучу, начиная с корня. Если текущая вершина принадлежит левой дуче, то она сама и ее ле- вое поддерево добавляются в левую дучу, после чего процедура рекурсивно применяется к правому поддереву. Наоборот, если текущая вершина принад- лежит правой дуче, то она сама и ее правое поддерево добавляются в правую дучу, после чего процедура рекурсивно применяется к левому поддереву. По- скольку высота дучи равна O(log n), эта операция занимает время O(log n).
На рис. 15.19 показано, как массив из примера выше разбивается на два массива таким образом, что первый содержит первые пять элементов, а второй – последние три. Вершина D принадлежит левой дуче, поэтому мы добавляем ее вместе с левым поддеревом в левую дучу. Далее, вершина
C принадлежит правой дуче, поэтому мы добавляем ее вместе с правым поддеревом в правую дучу. Наконец, вершина W добавляется в левую дучу, а вершина I – в правую.
S
A
N
D
W
I
C
H
0 1
2 3
4 0
1 2
9
S
3
A
6
N
1
D
8
W
9
I
4
C
5
H