Дерево по значениям

Второе применение дерева отрезков, внешне непохожее на первое: индекс дерева — не позиция в массиве, а значение.

В ячейке $x$ лежит, сколько раз значение $x$ уже встретилось. Тогда «сколько среди просмотренных чисел меньше $x$» — это сумма на отрезке значений $[1, x-1]$, то есть один запрос.

Инверсии за один проход

Инверсия — пара индексов $i < j$ с $a_i > a_j$. Идём слева направо и для каждого элемента спрашиваем, сколько уже встреченных больше него:

long long answer = 0;
for (int i = 0; i < n; i++) {
    answer += i - countAtMost(a[i]);   // все пройденные минус те, что не больше
    add(a[i], 1);
}

Тот же приём считает тройки $i < j < k$ с $a_i > a_j > a_k$: для каждого среднего элемента нужно знать, сколько слева больше и сколько справа меньше. Два прохода, потом перемножить и сложить.

Сжатие координат

Значения доходят до $10^9$, а дерево такого размера не построить. Заменим числа их номерами в отсортированном списке различных значений — сравнения от этого не изменятся, а размер дерева станет $n$.

std::vector<int> sorted = a;
std::sort(sorted.begin(), sorted.end());
sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
for (int &x : a) x = std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;

Подробнее: «Сжатие координат».

Динамика с переходом через дерево

Дерево по значениям часто оказывается переходом динамики. Пример: количество возрастающих подпоследовательностей наибольшей длины.

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

Узнавать такие задачи надо по фразе «сумма (или максимум) по всем предыдущим, у которых значение меньше».

Про дерево Фенвика

Для сумм с прибавлением в точку есть структура вдвое короче — дерево Фенвика. Она умеет меньше (только обратимые операции, никаких минимумов, составных узлов и спусков в общем виде), но пишется в десять строк и быстрее по константе.

void add(int at, int delta) { for (; at <= n; at += at & (-at)) f[at] += delta; }
int sum(int at) { int r = 0; for (; at > 0; at -= at & (-at)) r += f[at]; return r; }

Практическое правило: если задача сводится к «прибавить в точку, спросить сумму префикса» — берите Фенвика. Как только нужен минимум, спуск или составной узел — дерево отрезков.

Про выражение at & (-at): «Битовые операции».