Устройство и построение

Разобьём массив пополам, каждую половину — пополам, и так до отдельных элементов. Получится дерево, в каждом узле которого хранится ответ для его отрезка.

                 [1..8]
         [1..4]           [5..8]
     [1..2]  [3..4]   [5..6]  [7..8]
     1  2    3  4     5  6    7  8

Всего узлов меньше $2n$: листьев $n$, внутренних — на один меньше. Высота дерева — $\lceil \log_2 n \rceil$.

Нумерация

Корень — вершина 1, дети вершины $v$ — это $2v$ и $2v + 1$. Такая нумерация избавляет от указателей: всё дерево живёт в одном массиве.

std::vector<long long> tree(4 * n);

void build(int v, int tl, int tr) {
    if (tl == tr) { tree[v] = a[tl]; return; }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

Построение обходит каждый узел один раз: $O(n)$.

Почему 4n

Узлов меньше $2n$, но при такой нумерации номера не идут подряд: если $n$ не степень двойки, дерево получается неровным, и максимальный номер может превысить $2n$.

Оценка сверху такая. Достроим $n$ до ближайшей степени двойки $s$; тогда дерево полное, узлов ровно $2s - 1$, и все номера меньше $2s$. Поскольку $s < 2n$, все номера меньше $4n$.

Отсюда правило: выделяйте $4n$ и не думайте. Попытка сэкономить и выделить $2n$ приводит к выходу за границы массива: уже при $n = 6$ максимальный использованный номер равен 13, а $2n = 12$.

Оценка $4n$ не запас «на всякий случай», а почти точная граница. Перебор по всем $n$ до 20 000 даёт наибольшее отношение $3{,}954$ — при $n = 16512$ максимальный номер равен 65 281. Урезать до $3n$ тоже нельзя: впервые не хватает уже при $n = 36$, где номер доходит до 113.

Альтернатива: дополнить до степени двойки

Второй способ — сразу дополнить массив нейтральными элементами до длины $s = 2^k$. Тогда дерево полное, хватает ровно $2s$ ячеек, а листья лежат в $[s, s + n)$ и адресуются напрямую.

Это основа итеративной реализации, которая короче и быстрее рекурсивной.

Плата — до вдвое большая память в худшем случае: при $n = 2^k + 1$ дополнение почти удваивает длину.