Дерево отрезков на частоты: подсчёт количества вхождений значения на отрезке индексов?
Нужно поддерживать массив, где бывают точечные изменения значений, и отвечать на запрос «сколько раз значение v встречается среди a[l..r]». Как организовать дерево отрезков под подсчёт частот, чтобы и обновление, и запрос были логарифмическими?
2 ответа
Если множество возможных значений V небольшое (скажем, до ~50–100), держите в каждом узле дерева массив счётчиков длины V: cnt[v][value] = сколько раз value встречается в подотрезке узла. Слияние — поэлементная сумма массивов детей.
int cnt[4*N][V]; // V — число различных значений
void update(int v, int tl, int tr, int pos, int oldVal, int newVal) {
cnt[v][oldVal]--; cnt[v][newVal]++;
if (tl == tr) return;
int tm = (tl + tr) / 2;
if (pos <= tm) update(2*v, tl, tm, pos, oldVal, newVal);
else update(2*v+1, tm+1, tr, pos, oldVal, newVal);
}
int query(int v, int tl, int tr, int l, int r, int val) {
if (l > r) return 0;
if (l == tl && r == tr) return cnt[v][val];
int tm = (tl + tr) / 2;
return query(2*v, tl, tm, l, min(r,tm), val)
+ query(2*v+1, tm+1, tr, max(l,tm+1), r, val);
}
Запрос O(log n) на конкретное значение, обновление O(log n). Но память O(n·V) — годится только при маленьком V.
Если V большое (значения до 10^9), такой подход невозможен — нужен другой инструмент (см. второй ответ).
Когда значений много, держать счётчик каждого в каждом узле нельзя — MLE. Стандартный приём: один дерево/Фенвик на каждое значение, но не статически, а через индексы. Сожмите значения; для каждого значения храните отсортированный список позиций, где оно встречается (std::vector или std::set). Тогда «сколько v на [l, r]» = бинпоиск в списке позиций v: upper_bound(r) - lower_bound(l) за O(log n). Точечная вставка/удаление позиции в set — O(log n).
map<int, set<int>> pos; // значение -> множество позиций
// запрос:
auto& s = pos[val];
int c = distance(s.lower_bound(l), s.upper_bound(r)); // O(размера ответа)!
Осторожно: distance по set — линейный. Чтобы получить честный O(log n) счёт на отрезке для большого V, держите для каждого значения Фенвик по позициям или используйте merge sort tree / wavelet tree. Выбор зависит от того, нужны ли обновления и какой диапазон значений.