Итеративное дерево отрезков (bottom-up) на массиве 2n — как оно работает?
Слышал, что есть короткое итеративное дерево отрезков на массиве размера 2n без рекурсии — оно быстрее по константе. Как там устроены update и query? Не понимаю, почему запрос идёт «снизу вверх» и почему именно такие сдвиги индексов.
2 ответа
Идея: листья лежат подряд в t[n..2n-1], а внутренний узел i — это t[2i] и t[2i+1]. Никаких дыр, поэтому хватает ровно 2n.
int n;
long long t[2 * 100000];
void build() { // листья уже в t[n..2n-1]
for (int i = n - 1; i > 0; --i)
t[i] = t[2*i] + t[2*i+1];
}
void update(int p, long long val) { // a[p] = val
for (t[p += n] = val; p > 1; p >>= 1)
t[p>>1] = t[p] + t[p^1];
}
long long query(int l, int r) { // сумма на [l, r)
long long res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++];
if (r & 1) res += t[--r];
}
return res;
}
В query мы идём от листьев вверх: если левая граница l — правый ребёнок (l & 1), его поддерево целиком входит в ответ, берём и сдвигаем l. Симметрично для правой границы. query работает на полуинтервале [l, r).
Сложность: build O(n), update O(log n), query O(log n). Память ровно 2n. Константа меньше, чем у рекурсивного, и нет накладных расходов на стек.
Важная оговорка: эта короткая итеративная форма «из коробки» работает для коммутативных операций (сумма, xor, min, max), потому что при слиянии мы добавляем куски слева и справа в произвольном порядке. Для некоммутативных операций (например, перемножение матриц для линейной рекурренты) порядок важен — нужно копить отдельно левый и правый аккумуляторы и в конце слить их в правильном порядке:
// res_l собираем слева-направо, res_r справа-налево
T resl = ID, resr = ID;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) resl = combine(resl, t[l++]);
if (r & 1) resr = combine(t[--r], resr);
}
return combine(resl, resr);
Иначе получите WA на тестах, где a∘b != b∘a.