Заметим, что фактически в данном случае ключ для какой-то вершины — это количество вершин, меньших неё.
Красивая формулировка, как раз так вот и сделал.
Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое поддерево — накапливаемая сумма не меняется, а если идём в правое — увеличивается на cnt(t->l)+1.
И вы действительно время точнее одной аттосекунды получали?
Нет, конечно. Я использую ctrl-c ctrl-v, примерный результат по времени дает, что вполне сойдет. Заниматься максимальным точным сравнением времени выполнения не буду.
Красивая формулировка, как раз так вот и сделал.
Все умное до меня уже было написано )
Не очень понял, что здесь имеется ввиду. Вставка поддерева?
Сократил так, binary в b. Не сильно в терминологию углублялся, исправлю.
Это делалось не под конкретную задачу, а от нечего делать. За последние лет 8 я только один раз стэк писал для работы)
Нет, про это не слышал.
Нет, конечно. Я использую ctrl-c ctrl-v, примерный результат по времени дает, что вполне сойдет. Заниматься максимальным точным сравнением времени выполнения не буду.
Этим вопросом занялся от нечего делать )
Для таких можно компилятор правильный подсунуть, который будет вкомпиливать правильные дополнения )