Структуры данных для выполнения интервальных запросов

Постановка задачи
Пусть в памяти хранится последовательность из n элементов.
Такие запросы называют интервальными, потому что они затрагивают целый интервал значений.

Терминология

Классификация задач
Если элементы последовательности не изменяются (не предусмотрено выполнение операции модификации элемента), то в названии задачи фигурирует слово статическая (англ. static), иначе– динамическая (англ. dynamic).

Классификация задач
Если сначала все интервальные запросы поступили (после чего они все могли быть проанализированы), а только потом формируются ответы на них, то говорят про офлайн (англ.off line) версию задачи.
запрос-1
запрос-2
…
запрос-k
ответ-1
ответ-2
…
ответ-k
Если же поступает запрос, сразу даётся на него ответ и только после ответа на предыдущий запрос идёт следующий запрос, то говорят про онлайн (англ. оnline) версию задачи.
запрос-1
ответ-1
запрос-2
ответ-2
…
запрос-k
ответ-k
Мы будем в нашей лекции рассматривать online версию задачи.

Постановка задачи
Можно ли это сделать быстрее?

Постановка задачи
Покажем (на примере задач о сумме и минимуме на интервале), что с помощью специальных структур:
корневая эвристика;
дерево отрезков;
разрежённая таблица;
выполнить интервальный запрос можно быстрее.
При этом сначала над данными выполняют препроцессинг (предподсчёт) − предварительная подготовка, которая в последующем позволит эффективно обрабатывать запросы. Очевидно, что время предподсчёта должно быть не больше, чем суммарное время ответа на все запросы.

Задача RSQ

Задача RSQ. Обычный массив
Время работы:
хотелось бы быстрее
11
0

Задача RSQ. Префиксные суммы
Выполним предподсчёт

Задача RSQ. Префиксные суммы
Время на запрос суммы:

Задача RSQ. Префиксные суммы
Время на запрос модификации:
10
13
20
25
27
33

Задача RSQ. Префиксные суммы

Оценки

Промежуточный вариант
Одна операция быстрая, вторая медленная
Нужно компромиссное решение
Модификация
Сумма

RSQ. Блоки
Выполним предподсчёт
A
B
0
1
2
3
4
0
1
2
3
4
n=30
k=6
5
6
7
29
8
24

RSQ. Блоки
Удобно нумеровать блоки с нуля (на рис. размер блока k=6)
A
B
0
1
2
3
4
0
1
2
3
4
5
6
7
29
8
24
9
10
11
12
18

Выполнение операций
A
B
0
1
2
3
4
0
1
2
3
4
5
6
7
29
8
k=6
def Add(self, i, x):
self.a[i] += x
self.b[i // self.k] += x

Выполнение операций
A
B
0
1
2
3
4
0
1
2
3
4
5
6
7
29
8
24
n=30
k=6

Выполнение операций
A
B
0
1 (=jl)
2 (=jl+1)
3
4 (=jr)
0
1
2
3
4
5
6
7
29
8
24
n=30
k=6
def FindSum(self, l, r):
jl = l // self.k
jr = r // self.k
if jl == jr: # same block
return sum(self.a[l:r])
else:
return (
sum(self.a[l:((jl + 1) * self.k)]) +
sum(self.b[(jl + 1):jr]) +
sum(self.a[(jr * self.k):r]
)

Выполнение операций
A
B
0
1
2
3
4
0
1
2
3
4
5
6
7
29
8
24
n=30
k=6
Каким лучше выбрать размер блока k?

Оптимальный размер блока

Пример реализации
class Summator:
def __init__(self, a):
self.a = a
self.k = floor(sqrt(len(a))) self.b = []
for i in range(0, len(a), self.k):
bsum = sum(self.a[i:(i + self.k)])
self.b.append(bsum)
def Add(self, i, x):
self.a[i] += x
self.b[i // self.k] += x
def FindSum(self, l, r):
jl = l // self.k
jr = r // self.k
if jl == jr: # same block
return sum(self.a[l:r])
else:
return (
sum(self.a[l:((jl + 1) * self.k)]) +
sum(self.b[(jl + 1):jr]) +
sum(self.a[(jr * self.k):r]
)

Оценки

Дерево отрезков
Дальнейшим развитием идеи разбиения на блоки будет следующее:

Пример дерева отрезков для задачи RSQ
a
22
6
13
12
10
7
2
9
9
1
34

Дерево отрезков. Число вершин

Дерево отрезков. Хранение
Нет необходимости хранить указатели/ссылки
Для хранения вершин дерева будем использовать массив (по аналогии с тем, как была реализована на массиве бинарная куча)
Индексация в массиве с единицы (1 — корень)
v
2v
2v+1

Дерево отрезков. Хранение
26
16
10
9
7
3
2
5
6
1
1
2
3
4
5
6
7
10
11
14
15
n=6
Количество реально занятых ячеек равно 2n-1=11.
a
t

Дерево отрезков. Хранение
74
34
40
22
12
6
8
4
1
2
3
4
5
6
9
10
t
20
2
1
33
12
11
7
8
0
6
12
11
34
13
14
15
30
31
используемая память
неиспользуемая память

Дерево отрезков. Хранение
В том случае, когда n не является степенью 2, дерево не является полным, из-за чего в массиве могут быть неиспользуемые ячейки.
Чтобы места гарантированно хватило, можно выставить размер массива 4n.

Дерево отрезков. Построение
def DoBuild(a, t, v, tl, tr):
if tr - tl == 1:
t[v] = a[tl]
else:
m = (tl + tr) // 2
DoBuild(a, t, v=2*v, tl=tl, tr=m)
DoBuild(a, t, v=2*v+1, tl=m, tr=tr)
t[v] = t[2*v] + t[2*v+1]
def Build(a, n):
t = [0] * 4*n
DoBuild(a, t, v=1, tl=0, tr=n)
return t

Дерево отрезков. Построение
61
23
38
2
21
9
7
14
v=1
v= 2
v=3
v=4
v=5
v=6
v=10
t
16
13
v=11
7
29
v=14
v=15
a
[0,6)
[0,3)
[3,6)
def DoBuild(a, t, v, tl, tr):
if tr - tl == 1:
t[v] = a[tl]
else:
m = (tl + tr) // 2
DoBuild(a, t, v=2*v, tl=tl, tr=m)
DoBuild(a, t, v=2*v+1, tl=m, tr=tr)
t[v] = t[2*v] + t[2*v+1]
[4,6)
[5,6)
[4,5)
[3,4)
[0,1)
[2,3)
[1,2)
61
23
38
2
21
9
29
7
14
16
13
[1,3)
def Build(a, n):
t = [0] * 4*n
DoBuild(a, t, v=1, tl=0, tr=n)
return t
n=6

Дерево отрезков. Модификация
def DoAdd(t, v, tl, tr, i, x):
if tr - tl == 1:
t[v] += x
return
m = (tl + tr) // 2
if i < m:
DoAdd(t, v=2*v, tl=tl, tr=m, i=i, x=x)
else:
DoAdd(t, v=2*v+1, tl=m, tr=tr, i=i, x=x)
t[v] = t[2*v] + t[2*v+1]
def Add(t, n, i, x):
DoAdd(t, v=1, tl=0, tr=n, i=i, x=x)

Дерево отрезков. Модификация
def DoAdd(t, v, tl, tr, i, x):
if tr - tl == 1:
t[v] += x
return
m = (tl + tr) // 2
if i < m:
DoAdd(t, v=2*v, tl=tl, tr=m, i=i, x=x)
else:
DoAdd(t, v=2*v+1, tl=m, tr=tr, i=i, x=x)
t[v] = t[2*v] + t[2*v+1]
def Add(t, n, i, x):
DoAdd(t, v=1, tl=0, tr=n, i=i, x=x)
61
23
38
2
21
9
7
14
v=1
v= 2
v=3
v=4
v=5
v=6
v=10
16
13
v=11
7
29
v=14
v=15
a
[0,6), m=3
[3,6), m=4
[4,6), m=5
[4,5)
61
23
38
2
21
9
29
7
14
16
13
21
i=4, x=5
21
34
43
66
21
34
43
66
[4,5)

tr
tl=m
tr=m
tl
tl
tr
tl=m
tl
tr
tr=m
r
l
r
l
l
r
Дерево отрезков. Сумма
def DoFindSum(t, v, tl, tr, l, r):
if l == tl and r == tr:
return t[v]
m = (tl + tr) // 2
if r <= m:
return DoFindSum(t, v=2*v, tl=tl, tr=m, l=l, r=r)
if m <= l:
return DoFindSum(t, v=2*v+1, tl=m, tr=tr, l=l, r=r)
return (
DoFindSum(t, v=2*v, tl=tl, tr=m, l=l, r=m) +
DoFindSum(t, v=2*v+1, tl=m, tr=tr, l=m, r=r)
)
l=l
r=m
l=m
r=r
a

Дерево отрезков.
Сумма. Пример
68
20
48
9
11
26
3
8
t
16
6
22
a
[0,9)
[0,4)
[4,9)
[6,9)
[7,9)
[6,7)
[4,6)
[0,2)
[3,4)
[2,3)
[2,4)
n=9
2
7
[0,1)
[1,2)
14
12
[4,5)
[5,6)
1
5
[7,8)
[8,9)
7+
Найти сумму на отрезке [1,7).
Cумма на отрезке [1,7):
11+
16
26+
=60

Оценка времени работы

Оценка времени работы
остановка
спуск только вправо
(или только влево)
спуск в обе стороны

Доработки

Оценка времени работы

Оценки

Статическая задача RMQ
Cтатическая online задача
RMQ — Range Minimum Query
(запрос минимума на отрезке)

Статическая задача RMQ

Статическая задача RMQ
A
Так как каждый элемент таблицы по рекуррентному соотношению
T
может быть вычислен за константу, то время предподсчёта:

Разрежённая таблица
Идея — разреди́ть таблицу, убрать часть информации
Будем хранить минимумы для тех интервалов, длины которых являются степенями двойки
Такая структура называется sparse table (рус. разрежённая таблица)

Разрежённая таблица

Sparse table. Пример

Разрежённая таблица
Предположим, что
Оценим число «лишних» ячеек в таблице.

Ответ на запрос

Ответ на запрос

Свойства бинарного отношения минимума
Ассоциативность (выполнять операции можно в произвольном порядке, т.е. допускается любой порядок расстановки скобок):
Коммутативность (можно располагать элементы в произвольном порядке, переставляя их):
Идемпотентность (благодаря этому свойству мы сможем работать на пересекающихся отрезках):

Свойства бинарного отношения минимума
r
a

Пример
1
1

Ответ на запрос. Примеры

Упражнение 1

Упражнение 2

Общие задачи
0.2 Задача о сумме (реализация структур для интервальных запросов - сумма на отрезке)
iRunner