Привет, Codeforces!
В этом посте я бы хотел поделиться тем, как я пишу Дерево отрезков, объясню, почему я это делаю классом, а так же какие у этого плюсы и минусы.
Чтобы не быть голословным я бы хотел рассмотреть свое решение на конкретной задаче (осторожно, идеи к решению)
Что в этом написании особенного
Основная моя идея в том, чтобы реализовать ДО как класс
Это позволяет использовать для двух деревьев отрезков более понятный интерфейс sgb.upd(l2, r2 + 1)
sga.upd(l1, r1 + 1)
sga.get(l1, r1 + 1) + sgb.get(l2, r2 + 1)
вместо upd1(l1, r1 +1)
upd2(l2, r2 + 1)
и get1(l1, r1 + 1) + get2(l2, r2 + 1)
А если количество деревьев переменно, то по другому это вроде не закодить(по крайней мере я не умею).
Другая не менее важная идея состоит в том, чтобы реализовать две функции каждого типа например get(int v, int l, int r, int L, int R) и get(int L, int R)
Я хочу получить значение на отрезке и не хочу думать о параметрах которые не влияют на запрос. Поэтому get(int v, int l, int r, int L, int R) является внутренним интерфейсом, который используется только для подсчета результата и не вызывается снаружи.
Так же я использую структуру, которая поддерживает приватные и публичные поля.
Это чисто эстетическое предпочтение, когда редактор подсказывает только те функции, которые могут быть вызваны снаружи. против
Почему я пишу именно так
Однажды, когда я писал отбор в сириус, была задача в которой n исходная и n ДО не совпадали. И в функции запросов и обновления я писал неверное значение n. За время отбора я так и не раздебагал это. Как итог мне не хватило совсем чуть чуть баллов до прохода. После этой грустной истории я разработал для себя некий стандарт, которому стараюсь соответствовать.
Заключение
Плюсы
- Помогает не думать над тем, какой параметр передавать в запрос (Например в приведенной выше задаче, в одном случае размер равен n/2 + 1 а в другом n/2. Подобная ошибка в пару символов может стоить нескольких минут, а в худшем случае и десятков).
- Эстетично приятно.
- Пишется шаблонно (сначала mrg, потом build, дальше push и тд).
- Легко заменить. Нужно только изменить функцию mrg и поля у вершины.
- Подходит для задач, где нужно одинаковое ДО для нескольких массивов
Минусы
- Дольше работает. Во-первых, как известно статмасивы всегда лучше векторов по скорости, однако создать класс со статмасивом лично у меня не получилось (код крашается). Во-вторых вызов функции из класса вроде работает дольше, чем обычной функции
- Дольше пишется.
Вывод
Объективно минусы существенные по сравнению с плюсами. Однако я считаю, что мой способ написания имеет место быть. Он помогает избежать ошибок при написании и использовании не очень внимательным людям (к которым я, конечно же, отношусь). Если решение получает TL заменить vec t; на pii t[MAXN] не составит большого труда. А функции в основном решении уже стоят где надо и с правильными параметрами.
Если писать ДО снизу то такой проблемы не будет
Какой "такой"? Если тебе надо будет использовать несколько до, то все равно придется писать класс, разве нет?
Нет, ты что, просто напиши функции
get1
get2
get3
add1
add2
add3
pushlol
pushkek
pushamogus
Я так делал до 10 класса, кста
Я вот все ещё так делаю)
Игорь, я твой фанат!!!!!!!
Он Иван)
В никнейме написано Игорь, значит Игорь!!!!
Кек, че вы минусите. Зайдите на его профиль и посмотрите
Тебя на литературе учили определению иронии?
Почему ты не пишешь отдельный класс для вершины в ДО?
Вообще если для вершины нужно >2 полей то пишу структуру. Здесь было лень)
Ну все, слился получается
Виноват
можно же писать так:
ну конечно если нужно только одно ДО
А чему sz равно? Если это не константа, то не получится
Хотя если до одно, то скорее всего размер действительно почти всегда константный. Просто если есть способ писать всегда одинаково, то почему бы и нет
ну я пишу как на кф еду, sz = 1 << (ceil(log(n) / log(2))
Я посмотрел твою посылку 125408125. Такое не работает в классах, к сожалению.![](/predownloaded/39/a6/39a6c04e29975d1a2c5848313a642c16e1b91bd0.jpg)
Поздравляю. Осталось переделать на любой тип, научится передавать merge и подобное, и избавиться от
4 * n
, и будет дефолт.P. S.
...статмасивы всегда лучше векторов по скорости
— откуда инфа?Опыт + информация от других. Могу привести код в котором переписывание вектора на статмасив ускорило почти в 2 раза код(но речь не про до совсем)