и как результат - после поиска одного пути уже вся память была бы забита

кстати, есть ли гарантии, что  длина пути не меньше, чем k, для которого ищем статистику?

Есть набор символов (например А Б С Д Е), нужно составить все возможные пары из этих символ, при этом например АБ = БА. Есть какой то нормальный алгоритм делающий такое. Или только вложенными циклами?

а вложенные циклы это не нормальный?

for (i = 0; i < n; i++)
  for (j = i+1; j < n; j++)
    printf("%c%c", sym[i], sym[j]);

Ну вот я имел ввиду не такое) Просто, мне нужно сделать подобное для стобцов матрица, где строчки это последовательности символов. Т.е. тройной уже цикл получается.

все равно надо сгенерить все, а число итераций тут ровно то, которое нужно

Да

Решил так за log

Бинарным поиском перебираем значение элемента. Для него будем узнавать количество элементов < x. Пусть get(root, u) - количество таких элементов от корня до вершины u. Тогда мы можем найти количество на пути и понять k-ая порядковая ли эта статистика по формуле get(root,u) + get(root,v) - 2 * get(root, lca)
Чтобы находить количество таких за log , надо построить перс ДО от корня. Типо строим ДО для корня, потом новую версию для его сыновей, в которой log n вершин изменяются, остальные ведут на корня. Ну думаю ты знаешь что такое перс ДО.

Количество чисел <= x запрос суммы к нужной версии ДО

Если делать спуск по одновременно трем деревьям, будет чистый лог

красиво

попробовать, что ли, там зарегиться и сдать варварство за полторалог

Хотя понял, что есть корень проще

для каждой вершины храним отсортированный массив значений в её sqrt(N) предках
Итого каждый запрос сводится к поиску k-го в объединении максимум sqrt(N) массивов, при этом создавать из них, а не поднимать из памяти, нам нужно только один

Лес персистентных ДО, как и в случае с массивом

Не все жадники являются матроидами.

В массиве мы спускаемся по двум ДО: на левой и правой границе. А тут по трем:
Два дерева для каждого из концов, и еще одно для из LCA.