Если всю структуру дерева формировать всю и сразу, то да. Однако, если создавать вершины только по необходимости, то выходит (в худшем случае) что-то около созданных вершин на один запрос.

При случайных запросах даже это не достигалось, эмпирически было похоже на памяти.

Не могу сходу оценить — эта последовательность имеет предел?

Она конечна :)

А вообще, я просто неправильно прочитал предыдущий комментарий, действительно, для long long int нужно создать корень, который будет весить 2^32, так что печально все.

Ну, подытоживая, скажу, что можно использовать для чисел бит до 45, наверное, более или менее адекватно.

Не, я имею в виду, можно ли как-то сжато оценить эту последовательность. Типа n/2+n/4+...=O(n). n+n/2+n/3+n/4+...=O(nlogn)

Ну, не более точно, но все же тут главное слагаемое — первое.

Выходит, расход памяти и времени порядка ?

Обычно оценивают время как , именно такое время тратится на поиск. С памятью разговор отдельный — при ленивом построении оценивают обычно амортизированно.

И какая амортизированная оценка?.. Вообще я слышал, что суммарная оценка времени не может быть ниже суммарной оценки памяти

Это безусловно. Окей, постараюсь внести предельную ясность.

Мы имеем структуру, которая занимает O(n) памяти с операцией за . Это самое обычное дерево.

Далее, мы пробуем сделать его ленивым. Мы, конечно же, теряем realtime-оценку на операции, потому что выделение массивов не бесплатное. Получаем, строго говоря, оценку .

Однако, в этом подходе разумно все же раздельно оценивать операции поиска и выделения памяти, по двум причинам.

Первая состоит в том, что оценка на количество появившихся вершин сильно завышена. Например, если запросов порядка 10⁷ при n = 2³², понятно, что дерево после первой сотни тысяч запросов будет более или менее полным и будет около константы выделений памяти на запрос.

Вторая в том, что аллокация памяти — вещь странная, зависящая от системного хипа, если мы едим память из хипа. Выделение сырого куска памяти может стоит случайно меньше, чем его размер.

Так а какая ассимптотика всё же выйдет в худшем случае? Есть тесты, где при ленивом построении выйдут все ?

Во-первых, там будет , а во-вторых, в это не верю, верю, однако, во что-то близкое к , но при достаточно малых q, видимо как раз порядка корня.

Хотя, можно за n / 2^k запросов отстроить все дерево, кроме последних k уровней, но что-то я туплю, сколько это добро выжрет памяти, есть подозрение, что около n^{1 - 2 - k}

Да, это вроде верно, но в среднем на запрос тогда получается , что с ростом k вроде как растет и худшее, что получается, это случай единственного запроса, который не очень интересный. Судя по всему, в этом и суть — сначала операции медленные, потом дело идет гораздо веселее.

Однако амортизировать это точнее как-то трудновато, можно поискать статьи на эту тему.

Выше написал что, если пытаться максимизировать память на запрос. С другой стороны видно, что для построения полного дерева нам будут нужны Ω(n) запросов и все они будут обработаны за в сумме.

A maxNum?

Во всех моих ответах подразумевалось, что n = maxNum, а где надо использовать количество запросов, оно обозначено за q. Так что я не очень понимаю, что не так с maxNum.

А, понял. Многовато выходит, да. А в сверхбыстром цифровом боре, который, вроде, с такой же ассимптотикой на запрос работает тоже есть такие проблемы с памятью?