Неделя 14

Лекция. BST и вырождение; идея сбалансированных деревьев без детальной реализации; sqrt-декомпозиция, sparse table, дерево отрезков без lazy.

Семинар. Вставка и обход BST, сумма на отрезке sqrt-декомпозицией, RMQ разреженной таблицей, точка и отрезок на дереве отрезков, сравнение со сканом.