#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/iterative-segment-tree

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/iterative-segment-tree

Repovive

Iterative Segment Tree - Segment Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Iterative Segment Tree

Non-recursive implementation

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.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!