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

Содержание

Слайд 2

Постановка задачи

Пусть в памяти хранится последовательность из n элементов.

 

Такие запросы называют интервальными,

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

Слайд 3

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

 

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

Слайд 4

Классификация задач

Если элементы последовательности не изменяются (не предусмотрено выполнение операции модификации элемента),

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

Слайд 5

Классификация задач

Если сначала все интервальные запросы поступили (после чего они все могли

Классификация задач Если сначала все интервальные запросы поступили (после чего они все
быть проанализированы), а только потом формируются ответы на них, то говорят про офлайн (англ.off line) версию задачи.

запрос-1
запрос-2

запрос-k

ответ-1
ответ-2

ответ-k

Если же поступает запрос, сразу даётся на него ответ и только после ответа на предыдущий запрос идёт следующий запрос, то говорят про онлайн (англ. оnline) версию задачи.

запрос-1
ответ-1
запрос-2
ответ-2

запрос-k
ответ-k

Мы будем в нашей лекции рассматривать online версию задачи.

Слайд 6

Постановка задачи

 

Можно ли это сделать быстрее?

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

Слайд 7

Постановка задачи

Покажем (на примере задач о сумме и минимуме на интервале), что

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

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

Слайд 8

Задача RSQ

 

Задача RSQ

Слайд 9

Задача RSQ. Обычный массив

 

Время работы:

хотелось бы быстрее

11

0

 

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

Слайд 10

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

 

Выполним предподсчёт

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

Слайд 11

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

 

 

 

 

Время на запрос суммы:

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

Слайд 12

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

 

 

 

 

Время на запрос модификации:

10

13

20

25

27

33

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

Слайд 13

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

 

 

 

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

Слайд 14

Оценки

 

Оценки

Слайд 15

Промежуточный вариант

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

Модификация
Сумма

 

 

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

Слайд 16

RSQ. Блоки

 

Выполним предподсчёт

 

A

B

0

1

2

3

4

0

1

2

3

4

n=30
k=6

5

6

7

29

8

24

RSQ. Блоки Выполним предподсчёт A B 0 1 2 3 4 0

Слайд 17

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

 

 

 

 

 

RSQ. Блоки Удобно нумеровать блоки с нуля (на рис. размер блока k=6)

Слайд 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] +=

Выполнение операций A B 0 1 2 3 4 0 1 2
x

 

Слайд 19

Выполнение операций

 

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 2 3 4 0 1 2

Слайд 20

Выполнение операций

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 //

Выполнение операций A B 0 1 (=jl) 2 (=jl+1) 3 4 (=jr)
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]
)

Слайд 21

Выполнение операций

A

B

0

1

2

3

4

0

1

2

3

4

5

6

7

29

8

24

n=30
k=6

 

Каким лучше выбрать размер блока k?

Выполнение операций A B 0 1 2 3 4 0 1 2

Слайд 22

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

 

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

Слайд 23

Пример реализации

class Summator:
def __init__(self, a):
self.a = a
self.k = floor(sqrt(len(a)))

Пример реализации class Summator: def __init__(self, a): self.a = a self.k =
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]
)

Слайд 24

Оценки

Оценки

Слайд 25

Дерево отрезков

 

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

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

Слайд 26

Пример дерева отрезков для задачи RSQ

 

a

22

6

13

12

10

7

2

9

9

1

34

 

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

Слайд 27

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

 

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

Слайд 28

Дерево отрезков. Хранение

Нет необходимости хранить указатели/ссылки
Для хранения вершин дерева будем использовать массив

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

v

2v

2v+1

Слайд 29

Дерево отрезков. Хранение

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

Дерево отрезков. Хранение 26 16 10 9 7 3 2 5 6

Слайд 30

Дерево отрезков. Хранение

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

 

используемая память

неиспользуемая память

Дерево отрезков. Хранение 74 34 40 22 12 6 8 4 1

Слайд 31

Дерево отрезков. Хранение

В том случае, когда n не является степенью 2, дерево

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

Слайд 32

Дерево отрезков. Построение

def DoBuild(a, t, v, tl, tr):
if tr - tl

Дерево отрезков. Построение def DoBuild(a, t, v, tl, tr): if tr -
== 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

Слайд 33

Дерево отрезков. Построение

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 -

Дерево отрезков. Построение 61 23 38 2 21 9 7 14 v=1
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

Слайд 34

Дерево отрезков. Модификация

def DoAdd(t, v, tl, tr, i, x):
if tr -

Дерево отрезков. Модификация 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)

 

Слайд 35

Дерево отрезков. Модификация

def DoAdd(t, v, tl, tr, i, x):
if tr -

Дерево отрезков. Модификация 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)

Слайд 36

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 ==

tr tl=m tr=m tl tl tr tl=m tl tr tr=m r 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

Слайд 37

Дерево отрезков. Сумма. Пример

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

Дерево отрезков. Сумма. Пример 68 20 48 9 11 26 3 8

Слайд 38

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

 

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

Слайд 39

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

 

остановка

спуск только вправо
(или только влево)

спуск в обе стороны

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

Слайд 40

Доработки

 

Доработки

Слайд 41

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

 

 

 

 

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

Слайд 42

Оценки

 

 

 

 

 

 

 

 

 

 

 

 

 

Оценки

Слайд 43

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

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

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

Слайд 44

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

 

 

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

Слайд 45

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

A

 

 

Так как каждый элемент таблицы по рекуррентному соотношению

 

 

T

может быть вычислен

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

Слайд 46

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

Идея — разреди́ть таблицу, убрать часть информации
Будем хранить минимумы для тех

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

Слайд 47

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

 

 

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

Слайд 48

Sparse table. Пример

 

Sparse table. Пример

Слайд 49

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

Предположим, что

 

 

Оценим число «лишних» ячеек в таблице.

 

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

Слайд 50

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

 

 

 

 

 

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

Слайд 51

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

 

 

 

 

 

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

Слайд 52

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

Ассоциативность (выполнять операции можно в произвольном порядке, т.е.

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

Слайд 53

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

r

 

a

 

 

 

 

 

 

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

Слайд 54

Пример

 

 

 

 

1

1

Пример 1 1

Слайд 55

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

 

 

 

 

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

Слайд 56

Упражнение 1

 

Упражнение 1

Слайд 58

Упражнение 2

 

Упражнение 2

Слайд 59

Общие задачи

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

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

iRunner