Что такое дерево отрезков и дерево Фенвика и когда они нужны?

Обе структуры решают задачу «запросы на отрезке плюс изменения элементов» за O(log n) на операцию, тогда как массив префиксных сумм отвечает за O(1), но обновляется за O(n).

Дерево отрезков

• Каждый узел хранит агрегат своего отрезка, корень — всего массива, листья — отдельных элементов; память около 4n в массивной реализации.
• Подходит любая ассоциативная операция: сумма, минимум, максимум, НОД.
• Ленивое проталкивание (lazy propagation) даёт и массовые обновления вида «прибавить x на [l, r]» за O(log n).

Дерево Фенвика (BIT)

• Массив длины n+1, где ячейка i отвечает за отрезок длины i & -i, заканчивающийся в i.
• Префиксная сумма и точечное обновление — O(log n), код в десяток строк, памяти ровно n.

class Fenwick {
  #t;
  constructor(n) { this.#t = new Array(n + 1).fill(0); }
  add(i, delta) { // i с 1
    for (; i < this.#t.length; i += i & -i) this.#t[i] += delta;
  }
  prefix(i) { // сумма a[1..i]
    let s = 0;
    for (; i > 0; i -= i & -i) s += this.#t[i];
    return s;
  }
}
// сумма на [l, r] = prefix(r) - prefix(l - 1)

Как выбрать

• Сумма или XOR с точечными изменениями — Фенвик: проще и быстрее по константе.
• Минимум на отрезке или массовые обновления — дерево отрезков: у минимума нет обратной операции, и разность префиксов не работает.

Коротко для собеседования

Префиксные суммы хороши, пока массив не меняется; если нужны и запросы на отрезке, и обновления, берут Фенвика или дерево отрезков за O(log n). Фенвик короче и быстрее для сумм, а для минимума и массовых обновлений нужно дерево отрезков, потому что у минимума нет обратной операции.