Как за O(n) инициализировать дерево Фенвика из готового массива вместо n обновлений?
Обычно я строю BIT, вызывая update n раз — это O(n log n). Если массив дан сразу, есть ли способ построить Фенвик за линейное время? И насколько это вообще критично?
2 ответа
Да, есть O(n) построение. Сначала кладём в t[i] само значение a[i], затем за один проход «проталкиваем» каждый узел в его родителя i + (i & -i).
void build(vector<long long>& t, const vector<long long>& a, int n){
// t размера n+1, a индексируется с 1
for (int i = 1; i <= n; ++i) t[i] += a[i];
for (int i = 1; i <= n; ++i) {
int parent = i + (i & -i);
if (parent <= n) t[parent] += t[i]; // префикс-сумма блока ушла родителю
}
}
Почему верно: к моменту обработки i его блок t[i] уже накопил сумму своего поддиапазона (узлы с меньшими индексами обработаны раньше), и мы прибавляем эту сумму ровно одному родителю. Итого O(n) время, O(n) память — против O(n log n) у наивного построения.
На практике это редко решает TL само по себе (n log n тоже обычно проходит), но в задачах с n до 10^7 и жёстким лимитом или с многократным пересозданием BIT линейное построение спасает. Запомнить полезно — стоит одну строчку.
Альтернатива той же сложности — посчитать префиксные суммы pref[] массива и положить t[i] = pref[i] - pref[i - (i&-i)] (сумма блока через два префикса). Тоже O(n). Выбирайте, что понятнее. Главное — не строить BIT n вызовами update, если массив известен заранее и n большое; а для маленьких n разница непринципиальна, не усложняйте код ради неё.