Семинар 2. Дерево отрезков

Разбор прошлого домашнего задания

Задача 1. Илья Мишуров

Задача 4. Эмиль Рахимов

Задачи с практики

1. Какие из пар операций дистрибутивны:

   а) $(\gcd, \mathrm{lcm})$;

   б) $(\mathrm{lcm}, \gcd)$;

   в) $(\gcd, +)$;

   г) $(+, \gcd)$;

   д) $(\wedge, \vee)$;

   е) $(\vee, \wedge)$;

   ё) $(\mathrm{whatever}, P_2)$ (здесь $P_2(x, y)=y$, $\mathrm{whatever}$ — произвольная операция); [не попало на практику]

   ж) $(P_2, \mathrm{whatever})$ [не попало на практику]?

2. Научимся избавляться от дистрибутивности. Какие из перечисленных операций дистрибутивны сами с собой:

   а) $+$;

   б) $\cdot$;

   в) $\min$;

   г) $\oplus$;

   д) $\wedge$;

   е) $\vee$;

   ё) $\gcd$;

   ж) $\mathrm{lcm}$?

   Что общего у всех подошедших примеров [ответ — это идемпотентные коммутативные операции (то есть $a\times a = a$, $a\times b=b\times a$)]? Как сделать дерево отрезков в неподошедших случаях?

3. а) Постройте дерево отрезков с методами set(i, x) и min(L, R).

   б) Как найти наименьший индекс минимума в дереве?

   в) Как найти число минимумов в дереве?

4. Научимся избавляться от декомпозируемости операции: рассмотрим массовую операцию, которая не выражается через двуместную операцию.

   а) постройте дерево отрезков с методами set(i, x) и $f(L, R)=\sum\limits_{i=0}^{R-L-1}{(-1)^ia_{i+L}}$;

   б) постройте дерево отрезков с методами set(i, x) и $f(L, R)=\sum\limits_{i=0}^{R-L-1}{ia_{i+L}}$;

5. Дан массив из чисел, постройте структуру данных с методом find(l, r, k): найти $k$-ю порядковую статистику среди $a_\ell, \ldots, a_{r-1}$.

   Подсказка 1. Постройте структуру данных, позволяющую добавить, удалить элемент из мультимножества и позволяющую найти $k$-ю порядковую статистику.

   Подсказка 2. Примените персистентность и решите исходную задачу.