Оптимальное дерево поиска

Даны $n$ элементов в возрастающем порядке и частоты обращений $f_1, \ldots, f_n$. Надо построить бинарное дерево поиска, минимизирующее

$$\sum_i f_i \cdot \mathrm{depth}(i)$$

где глубина корня равна нулю. Чем чаще элемент спрашивают, тем ближе к корню он должен стоять - но структура дерева поиска жёстко связана с порядком элементов, и просто «положить самый частый в корень» неверно.

Динамика по подотрезкам

Дерево поиска на отрезке элементов $[i, j]$ устроено так: какой-то элемент $k$ - корень, слева от него дерево на $[i, k-1]$, справа - на $[k+1, j]$.

Ключевое наблюдение: когда два поддерева подвешивают к новому корню, глубина каждого их элемента увеличивается на единицу. Значит, стоимость растёт ровно на сумму частот этих поддеревьев.

$$dp[i][j] = \min_{i \le k \le j} \Bigl( dp[i][k-1] + dp[k+1][j] + \sum_{t=i}^{j} f_t - f_k \Bigr)$$

Слагаемое $\sum f_t - f_k$ - это сумма частот всех элементов отрезка, кроме корня: у них глубина выросла на единицу, у корня она нулевая.

for (int len = 2; len <= n; len++)
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        long long sum = prefix[j + 1] - prefix[i], best = -1;
        for (int k = i; k <= j; k++) {
            long long value = (k > i ? dp[i][k - 1] : 0) + (k < j ? dp[k + 1][j] : 0) + sum - f[k];
            if (best < 0 || value < best) best = value;
        }
        dp[i][j] = best;
    }

Стоит $O(n^3)$: $O(n^2)$ отрезков, на каждом перебор корня.

Проверено: на 3000 наборах частот длины до 7 динамика дала тот же ответ, что и полный перебор всех бинарных деревьев поиска.

Оптимизация Кнута

Пусть $opt[i][j]$ - позиция корня, на которой достигается минимум. Оказывается, она монотонна:

$$opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$$

Тогда во внутреннем цикле не надо перебирать все $k$ - достаточно отрезка между двумя уже известными значениями. Суммарная длина всех таких отрезков на одной диагонали телескопически сворачивается в $O(n)$, и вся динамика становится $O(n^2)$.

for (int k = opt[i][j - 1]; k <= opt[i + 1][j]; k++) { ... }
opt[i][j] = argmin;

Проверено: на 28 949 отрезках из случайных наборов монотонность не нарушилась ни разу.

Измерено, во что это обходится по времени:

$n$	обычная динамика	с оптимизацией Кнута
250	7 мс	меньше 1 мс
1000	252 мс	6 мс
2000	2630 мс	34 мс

Практический вывод трезвый: до $n \approx 500$ оптимизация не нужна, обычная динамика укладывается в любой разумный лимит. Она начинает окупаться с $n$ порядка тысячи, зато там разница уже в десятки раз.

Условие применимости

Оптимизация Кнута работает не для любой динамики по подотрезкам. Достаточное условие - неравенство четырёхугольника на функцию стоимости $w$:

$$w(a, c) + w(b, d) \le w(a, d) + w(b, c) \quad \text{при } a \le b \le c \le d$$

плюс монотонность $w$ по вложению отрезков. Для суммы частот на отрезке оба условия выполняются, и потому приём применим.

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

Тот же приём ускоряет склейку куч и распил бруса.