CD
Оно не дает гарантий по асимптотике (только матожидание) и медленнее работает
зато ты пишешь его 1 раз на туре и используешь везде
Size: a a a
2020 August 01
K
тем, что оно хуже чем ДО
Иногда лаконичнее
MB
Иногда лаконичнее
ДД лаконичнее чем ДО?
K
ДД лаконичнее чем ДО?
Алгоритм с ним лаконичнее, чем алгоритм с до
A
зато ты пишешь его 1 раз на туре и используешь везде
а можно написать его 0 раз и использовать ДО
CD
а можно написать его 0 раз и использовать ДО
и получить задачу, которая ДО не решается?
S
Что такое ДД?
DK
Декартово дерево
2020 August 03
ПК
Как можно быстро переподвешивать дерево?
ПК
Ну т.е. нужно поддерживать что-нибудь на дереве и быстро его переподвешивать. Как можно это делать и что вообще можно так поддерживать?
G
Хз, я бы хранил бы лес в снм
MB
Ну т.е. нужно поддерживать что-нибудь на дереве и быстро его переподвешивать. Как можно это делать и что вообще можно так поддерживать?
какие операции нужны кроме переподвешивания?
ПК
какие операции нужны кроме переподвешивания?
Хочется узнать, какие операции на дереве можно так поддерживать, а какие — нельзя
MB
Хочется узнать, какие операции на дереве можно так поддерживать, а какие — нельзя
Ну например есть euler tour tree. Это эйлеров обход дерева, который положили в декартово дерево по неявному ключу. Он умеет в переподвешивания в том числе.
MB
Ну и многие операции можно свести к запросу на отрезке к ДД.
S
А простое дерево на массиве ему подойдёт?
S
Где индекс текущей клетки - номер родителя. В седжвике в первой главе описывалось.
MB
его переподвешивать O(N) занимает
S
его переподвешивать O(N) занимает
Можно после каждой операции переподвешивать в корень и будет О(1)
S
Но хз что ему надо ещё