Возможно, рейтинг и не показатель, но задач на персистентное дерево отрезков меньше, чем задач на другие более простые, но не менее важные темы. Мой вам совет : научитесь решать сначала задачи уровня div2 c, d / div1 a, b, которые достаточно часто есть в задачах посложнее как подзадачи.

А персистентное дерево отрезков отличается от обычного тем, что вместо того, чтобы обновлять информацию в вершине, мы создаем новую. Если какая-то часть дерева отрезков не обновлялась, то мы делаем ссылку на старую вершину. Отличается лиш процедура update, в которой мы каждый раз, когда копируем вершину , обновляем информацию в ней, а старую вершину оставляем без изменений. Асимптотика по времени такая же , по пам'яти мы тратим дополнительные m log n памяти, где m — количество запросов обновления, а n — количество листьев.

Я согласен, но зачем спустя 4 года после обсуждения писать этот коммент? Просто интересно, довольно часто вижу на кф такое, и не особо понимаю смысл.

Спасибо