1. Дан набор n ящиков, в каждом ящике k_i предметов. Требуется случайно выбрать один предмет.
А ящиков очень много. Самая первая идея - построим бинарное дерево. В висячие вершины запишем количества предметов в ящиках. Далее, в каждую вершину запишем сумму чисел её двух непосредственных потомков.
Пускай в корне оказалось число А. Теперь выбираем случайно число от 1 до А и идём от корня дерева к какой-то висячей вершине (нам нужно каждый раз выбирать к какому из потомков вершины мы должны перейти и это делается понятным образом).

Могут появляться новые ящики и изменяться количество объектов в ящиках.

2. Дана последовательность объектов. От объекта иногда ведут направленные рёбра к каким-то объектам с большими номерами. Степень каждого объекта не более с. А самих объектов очень много (N).
Два объекта называются несравнимыми, если между ними нет направленного пути.
Вопрос : как завести дополнительную структуру данных, чтобы быстро по паре объектов говорить сравнимы они или нет? Быстро - это log N или быстрее.(ясно, что это осмысленно только для объектов, у которых разность номеров порядка N)

----------------------------------------------------------------

1. Самое интересное, как строить такое дерево, чтобы матожидание количества операций для случайного выбора предмета было поменьше. Естественно, просто сбалансированное дерево не катит - если в одном ящике 1000 предметов, а в остальных 100 по одному, то одним из двух прямых потомков корня должен быть первый ящик.

Вторая идея : если для корня у левого потомка вес больше, чем у правого, то высота левого поддерева должна быть меньше, чем у правого.

Третья идея : надо сначала упорядочить все объекты по возрастанию, а потом все до какого-то места отдать левому поддереву, а после этого места - правому поддереву. Осталось определить место.

Ну а его надо определять минимизирую какую-нибудь энтропию - сумма весов ящиков в левой половине на логарифм их количества плюс то же самое для правых ящиков. Или минимизировать.

2. А вот тут никаких идей. Разве что умно дорисовать чуть-чуть стрелочек. Таким образом : бывают седловые точки - такие точки А, что много путей от точек слева от А до точек справа от А проходят через А. Ну или что-нибудь похожее делать уже по ходу использования - типа ant colony.

это параллельно в ЖЖ - http://nikaan.livejournal.com/135129.html

По поводу первой задачи - надо ещё подумать.

Вторая же - это, иными словами, задача на достижимость в ориентированном ациклическом графе ("reachability in directed acyclic graphs"). Задача с очень простой формулировкой, и хотя для деревьев она решается вообще за O(1) на запрос, для DAG'ов, насколько я понимаю, даже нет не-рандомизированного алгоритма хотя бы за O(log) (по крайней мере, мне не удалось найти). Нашлась статья "Average case analysis of fully dynamic reachability for directed graphs", там вроде бы за log решается, но рандомизированным алгоритмом, и слегка навороченным (т.к. они решают задачу для меняющихся графов). Ссылаются на статью Karp "The transitive closure of a random digraph" (http://www.icsi.berkeley.edu/cgi-bin/pubs/...on.pl?ID=000546), в которой описан алгоритм, который для случайных графов за O(M) строит структуру данных (транзитивное замыкание в компактном виде), по которой можно за O(1) выполнять запросы на достижимость.

Если есть время и желание - можно попробовать реализовать, что там у Карпа написано.
А, может, устроит простой алгоритм - за N^2 / 32 времени и памяти для каждой вершины предпосчитать все достижимые из неё (в виде битовых масок)?

Первая задача - по всей видимости, известнейшая задача об оптимальном дереве поиска.

Первый способ решения - за N^3 - динамическим программированием. Для начала, по всей видимости, верно, что объекты надо предварительно отсортировать. Далее, мы хотим решить задачу для объектов в отрезке [l;r]. Тогда ответ для этого отрезка D[l,r] можно найти, просто перебрав, где находится искомая "середина"; обозначим её через m, тогда D[l,r] = SUM[l,r] + min { D[l,m] + D[m+1,r] } для всех m=l..r-1. Базой динамики является D[i,i] = 0. Тем самым, ответ для каждого состояния [l,r] можно найти, зная ответы для меньших состояний (вложенных отрезков). Итого асимптотика N^2 * N = N^3.

Второй способ - это хитрый хак поверх предыдущего решения: утверждается, что если мы хотим найти искомую серединку m для состояния (i,j), то она будет находиться между серединками для состояния (i,j-1) и (i+1,j). Доказательства этого факта я не знаю, по-моему, оно есть в Кнуте. Всё, в результате асимптотика нахождения m снижается до O(1) в среднем, и итого N^2.

Впрочем, это всё решения "статической" задачи, без добавляющихся ящиков. Как прикрутить сюда ещё и динамичность - это предмет отдельного обдумывания 

2. спасибо - но N^2 слишком велико  поэтому буду читать, что там пишут. Я так думаю, надо построить транзитивное замыкание, но не всё - а наиболее содержательную часть, что-ли. Компромисс между памятью и скоростью 
посмотрим, в общем, на практике.

1. Вся проблема именно в том. что всё это динамическое и постоянно перестраивается.
И у меня сильное подозрение. что наилучшее дерево при изменении пары весов может перестроиться кардинально.
Я предлагаю точку, где делить попалм искать так  min log(k_1)*S_1 + log(k_2)*S_2 , где k_1, k_2 - количество предметов слева и справа отточки деления, а Ы_1бЫ_2 - сумма весов слева и справа.

Добавлено через 31 секунду
S_1, S_2 я имел в виду 

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

Надо ещё придумать пример, когда самое оптимальное дерево резкр меняется при добавлении ещё одной вершины 

А в проект это добавлять не хотят :( мол, и так хорошо работает, а времени нет.

Ну у меня тоже есть подозрение, что добавление и удаление вершин в такое дерево будет работать порядка его высоты, но нет времени думать над док-вом и реализацией этого...

Первая задача - это по сути оптимальное кодирование по Хаффману. Ящик - это символ, а количество предметов - частота.

Нет, к сожалению никакого параллелизма, кроме метафорического, я не уловил.
Т.е. цели вообще разные. Тут цель - быстро перестраивать и выбирать. Там - хранить.