AlgoPlus//structures / segment-tree
Read the theory

Segment Tree · Range Sum

Each node sums a slice; a range query takes whole nodes and splits the rest.

Array size
6
Range sum
—
sum […]
Legend
Visiting
Fully inside (summed)
Outside
AI Tutor Workspace
—
In a nutshell
A segment tree answers questions about ranges of an array — like 'what is the total of positions 3 through 9?' — without re-adding the numbers every time. Each node stores the answer for one slice of the array: the root covers the whole thing, and each node splits its slice between two children down to single elements. A range query grabs the few whole nodes that fall inside the asked-for range and only splits the ones that straddle its edges, so any range is answered in about log n steps instead of scanning every element.
Ready
Press play to begin the cinematic walkthrough.
A tree of ranges: each node sums a slice of the array. A range query takes whole nodes that fit and splits the ones that straddle — answering in O(log n) instead of O(n).
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Segment Tree · Range Sum.
Code Simulator
▼
1
def bst(root, val):
2
    # insert / search / traverse
3
    if root is None:
4
        return Node(val)  # Inserted/Found
5
    if val < root.val:
6
        root.left = bst(root.left, val)
7
    else:
8
        root.right = bst(root.right, val)
9
    # traversal order
10
    visit(root.val)  # Visit
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.