Итеративное дерево

Если дополнить массив нейтральными элементами до длины $s = 2^k$, дерево становится полным. Листья лежат в ячейках $[s, 2s)$, родитель ячейки $v$ — это $v / 2$.

int size = 1;
while (size < n) size <<= 1;
std::vector<long long> tree(2 * size, NEUTRAL);
for (int i = 0; i < n; i++) tree[size + i] = a[i];
for (int v = size - 1; v >= 1; v--) tree[v] = merge(tree[2 * v], tree[2 * v + 1]);

Изменение — подъём по пути

void update(int position, long long value) {
    int v = size + position;
    tree[v] = value;
    for (v >>= 1; v >= 1; v >>= 1) tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
}

Никакой рекурсии: просто идём вверх, пересчитывая узлы.

Запрос — два указателя навстречу

Отрезок задаётся полуинтервалом $[l, r)$, и два указателя ползут вверх, забирая узлы, которые целиком внутри:

long long query(int l, int r) {          // полуинтервал [l, r)
    long long result = NEUTRAL;
    for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
        if (l & 1) result = merge(result, tree[l++]);
        if (r & 1) result = merge(result, tree[--r]);
    }
    return result;
}

Условие l & 1 означает «мой родитель захватывает и то, что левее меня», поэтому узел надо забрать прямо сейчас. Симметрично для правой границы.

Где это не работает

Куски забираются в произвольном порядке: сначала левый, потом правый, потом снова левый. Для суммы, минимума, максимума, НОД и XOR это неважно — они коммутативны.

Но для составных узлов — максимальной суммы подотрезка, длины серии, скобочной последовательности — порядок важен, и наивная итеративная версия даёт неверный ответ.

Лечится двумя накопителями:

Node left = NEUTRAL, right = NEUTRAL;
for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
    if (l & 1) left = merge(left, tree[l++]);
    if (r & 1) right = merge(tree[--r], right);
}
return merge(left, right);

Куски левой границы приходят слева направо, правой — справа налево, и порядок восстанавливается.

Важно, что массив дополнен до степени двойки. В более экономной версии, где листьев ровно $n$, отрезок в ячейках оказывается «прокручен» относительно исходного массива, и порядок так уже не восстановить.

Проверено перебором на композиции линейных функций $x \mapsto ax + b$ — операции ассоциативной, но не коммутативной: версия с двумя накопителями совпала с эталоном на 120 000 запросах, версия с одним ошиблась на 17 243 из них.

Что выбрать

Итеративное дерево короче и быстрее — но не умеет отложенных операций без заметного усложнения и хуже читается при спуске.

Практическое правило: точечные изменения — итеративное, операции на отрезке — рекурсивное.