Да, теперь видно преимущество этого дерева перед остальными при больших U. Код, правда, чуть более сложный, но при написании больших проектах, где быстродействие важно, это дерево полезно использовать.
Спасибо за уточнение. Что-то я пропустил строки вставки элемента в пустое дерево.

P. S. Мда, мир тесен. Про это дерево вам рассказали в параллели A, или где ты натолкнулся на эту структуру?

Да, STL не индусы писали, но всё-таки у сета довольно большая константа. Мне кажется, что дерево ван Эмде Боаса стоит сравнивать по времени работы с деревом отрезков. У дерева отрезков время работы O(N*log(N)), причём константа не сильно большая, а так же оно поддерживает все необходимые вам операции. Что касается памяти, так вроде полностью заполненное дерево вад Эмде Боаса будет хранить более 2*N памяти (размер дерева отрезков) из-за хранения этих дополнительных aux k/2-деревьев.

И ещё остался вопрос по ассимптотике:

Асимптотика времени его работы будет все так же O(log(log(U))), она оценивается аналогично предыдущей версии функции insert. Необходимо лишь заметить, что если мы выполним вставку в aux, то следующий за ним insert будет работать за O(1), так как это поддерево будет пустым.

Не понятно, почему в случае вставки в aux следующий за ним insert работает за O(1). Ведь нам всё равно при выполнении insert придётся пройти те же самые log(k) уровней до 1-дерева, значит и функция T(k) время работы будет более сложно пересчитываться, разве нет?

Почему-то ничего не могу делать. Ни плюсовать, ни оставлять комментарий (окно ввода появляется, а после посылки выкидывает на главную и предлагает сохранить какую-то гифку. после входа в описание инициативы моего коментария не обнаруживается). Возможно это из-за уровня рейтинга. Тогда необходима таблица со списком возможностей при каждом уровне рейтинга.

А так идея проекта хорошая, поздравляю. А если и настоящая власть обратит на это внимание, то цены ей не будет))

Да, но эти доказательства не незаконны. Или какой закон/статью они нарушают?

Статья 137. Нарушение неприкосновенности частной жизни
Незаконное собирание или распространение сведений о частной жизни лица, составляющих его личную или семейную тайну…

Не думаю, что фото/видео подробностей нарушения является информацией о частной жизни и тайне нарушителя. Так что думаю, такие записи не попадают под 137 УК

Не будет его в 2012 году. Не будет. Гарантия.

Я бы сказал: «Не дожно быть его в 2012 году». Проблема с централизацией власти огромная, правда, адекватной альтернативы медвепуту и остальным фсбешникам нет. Ведь у власти нет никого «из народа»

Извиняюсь, проглядел я их) Да, тоже не нравятся. Хотя согласен с тем, что декартово дерево не сильно тривиально для понимания и в нём много особенностей, так что с его описанием я не спорю.

Вы рассматриваете какого-то идеального студента-учёного, который учится и проводит исследования ради науки, всего себя посвящает только науке, а питается только знаниями да воздухом. Согласен, что бывают и такие, но их единицы на фоне остальных. Просто у любого человека есть пирамида потребностей. И если не будут удовлетворяться основные из них за счёт стипендии и поддержки начинающих учёных, то тогда они будут меньше заниматься наукой, а то и вообще из неё уйдут, ради работы, которая предоставит средства к самостоятельному существованию.

А отмена стипендий только больше усугубит ситуацию. Просто всем придётся искать работу, ане наукой заниматься.

Вы ошиблись. Видимо, вы имели ввиду количество всех «подстрок» N^2. А мы рассматриваем только суффиксы. Суффикс — подстрока, конец которой совпадает с концом нашей строки. Таким образом, суффикс определяется своим началом, которых N

Я не в праве выкладывать такую информацию. Считаю, что это работа преподавателей, и им решать, где и что они хотят выложить в общественное пользование. Ведь у каждого ВУЗа есть свои секреты

Этот алгоритм где мне только не рассказывали, но в ЛКШ тоже было дело. Но идея возникла только сейчас, при подготовке к сессии. А что, про него рассказывали этой зимой?

Раз появились желающие… Но вообще-то я считаю, что алгоритм Ахо-Корасика более простой, чем Укконен, да и найти его описание тоже можно в больших местах. Но вот алгоритм Укконена я долго не мог найти, за исключением возможно всего пары мест: Ден Гасфилд «Строки, деревья и последовательности в алгоритмах» (причём там не очень понятно написано, и для тех, кто решил ознакомится с этим алгоримом впервые, будет сложно разобраться в нём), и как ниже указано, есть конспект Лифшица, но который я раньше не встечал. Поэтому и решил, что ещё одно описание алгоритму Укконена будет не лишним, что не могу сказать об алгоритме Ахо-Корасика.

PS. Возможно, через недельку-две смогу написать и про Ахо-Корасика.

Чего только не вытворяют с «Жизнью». Но такими темпами скоро можно будет и более сложные вычисления графики переносить на железо, освобождая проц.

И правда, уже в СМИ об этом начали писать:

http://lenta.ru/news/2010/10/25/thirty/
и
http://www.utro.ru/articles/2010/10/25/931938.shtml