Почему дерево отрезков заводят массивом размера 4n, а не 2n?
Везде вижу рекурсивное дерево отрезков с массивом tree[4*n]. Откуда берётся именно 4? Если n — степень двойки, листьев n, всего узлов 2n−1, выходит хватило бы 2n. Почему все пишут 4n и не боятся вылезти за границы?
2 ответа
Коэффициент 4 — это запас под индексацию node, 2*node, 2*node+1, начиная с корня node=1. Когда n не степень двойки, дерево достраивается до ближайшей сверху степени двойки, и нумерация по 2*node оставляет «дыры»: используемые индексы могут доходить почти до 4n.
Строгая оценка: пусть h = ceil(log2(n)) — высота. Полное двоичное дерево такой высоты имеет 2^(h+1)−1 узлов. В худшем случае (n чуть больше степени двойки, например n = 2^k + 1) это число близко к 4n. Конкретно граница такая:
размер >= 2 * 2^ceil(log2(n)) и это <= 4n
Поэтому 4*n гарантированно покрывает любой n при индексации с корнем 1. Если хочется впритык — берите 2 * (1 << (int)ceil(log2(n))), но 4n проще и безопаснее.
Если же строить итеративное дерево отрезков (bottom-up) на массиве t[2*n], листья кладутся в [n, 2n) подряд без дыр — там действительно хватает ровно 2n. Разница именно в схеме нумерации, а не в количестве «полезных» узлов. Память: O(n), время операций: O(log n).
Частая ловушка: люди берут 4*n, но забывают, что при динамическом n (например, читают n из ввода) надо аллоцировать vector<long long> tree(4*n) уже после чтения n. И ещё: если n=0 или n=1, 4*n может дать 0 или 4 — проверяйте краевые случаи, иначе tree[1] вылезет за границу при n=0. На олимпиаде безопаснее 4*n + 5.