Iterative Segment Tree

Iterative segment trees are faster in practice (no recursion overhead) and use exactly $2n$ space:

class IterativeSegTree:
    function init(arr):
        this.n = arr.length
        this.tree = array of 2*this.n zeros
        // Build: leaves at positions n to 2n-1
        for i from 0 to this.n - 1:
            this.tree[this.n + i] = arr[i]
        for i from this.n - 1 down to 1:
            this.tree[i] = this.tree[2*i] + this.tree[2*i+1]

Leaves are stored in positions $n$ to $2n-1$. Internal nodes in positions $1$ to $n-1$. Position $0$ is unused.

This layout is more cache-friendly and avoids the $4n$ space overhead.