Как офлайн посчитать «сколько чисел в префиксе ≤ значения» для пачки запросов через Фенвик?
Дан массив и q запросов вида «среди a[1..r] сколько элементов ≤ x». Онлайн с persistent-структурами сложно, но если можно отвечать офлайн — как это сделать Фенвиком? Кажется, тут нужна сортировка запросов.
2 ответа
Классический офлайн со сдвигом указателя по r. Сортируем запросы по возрастанию r. Идём по массиву слева направо, добавляя a[i] в BIT частот (по сжатым значениям). Когда указатель дошёл до r запроса — отвечаем query(rank(x)) = сколько добавленных (то есть из [1..r]) элементов имеют значение ≤ x.
struct Q { int r, x, id; };
// сжали значения a и x-ы в общие ранги (с 1)
sort(queries.begin(), queries.end(),
[](const Q& a, const Q& b){ return a.r < b.r; });
BIT bit(maxRank);
vector<long long> ans(queries.size());
int ptr = 1;
for (const Q& qu : queries) {
while (ptr <= qu.r) { bit.update(rankOf(a[ptr]), 1); ++ptr; }
ans[qu.id] = bit.query(rankLE(qu.x)); // ≤ x
}
rankLE(x) — позиция последнего сжатого значения ≤ x (через upper_bound). Сложность: сортировка O(q log q), добавления суммарно n раз по O(log n), запросы — q раз по O(log n). Итого O((n+q) log n) время, O(n+q) память. Указатель по r монотонно растёт — это и есть «два указателя» поверх Фенвика.
Если в запросе ещё и левая граница l (отрезок [l..r], а не префикс), офлайн по одному указателю не хватит — раскладывайте каждый отрезочный запрос на разность двух префиксных (f(r,x) - f(l-1,x)) и обрабатывайте 2q префиксных запросов тем же сканом. А если нужен онлайн ответ — тогда уже persistent BIT / persistent segment tree (wavelet-подобные структуры), но это заметно тяжелее и по коду, и по памяти; на контесте офлайн почти всегда проще, если порядок запросов не обязателен.