Семинар 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. Примените персистентность и решите исходную задачу.