Skip to content
Hello Python
Data Structure1 Practice2 Interview

Segment Tree

Range-query tree supporting logarithmic aggregation and point or lazy range updates. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Segment Tree when the prompt's constraints and required operations match this shape: Range-query tree supporting logarithmic aggregation and point or lazy range updates.

Pybit studies a professional Segment Tree interview workspace with precise technical objects.
On this page · Nodes Own Explicit Ranges

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Segment Tree Code Labs

Nodes Own Explicit Ranges

Every node owns a contiguous interval and stores one aggregate for it. Leaves own individual elements; a parent combines its two child ranges. The combine operation must be associative, and a disjoint contribution uses an identity such as 0 for sum or infinity for minimum.

Build and Query Disjoint Cover

Build bottom-up by combining children. To answer a range query, select stored nodes whose intervals are disjoint and whose union is exactly the requested range. Combining those nodes once each yields the result in O(log n) for a standard balanced segment tree.

Query Static Segment Ranges

Reference
def segment_range_query(values, queries):
    return [sum(values[left:right + 1]) for left, right in queries]
Practice

Implement segment_range_query(values, queries). Return the inclusive sum for each [left, right] query without mutating values.

Public tests

  • Verify inclusive query boundaries

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Propagate Point Updates

Change the leaf, then recompute every ancestor on its root path. Only O(log n) nodes own a range containing that point. The parent invariant—tree[node] = combine(left, right)—must hold again before the update returns.

Maintain Segment-Tree Range Sums

Reference
def segment_tree_ranges(values, operations):
    size = len(values)
    tree = [0] * (2 * size)
    tree[size:] = values
    for index in range(size - 1, 0, -1):
        tree[index] = tree[2 * index] + tree[2 * index + 1]
    def range_sum(left, right):
        left += size
        right += size + 1
        total = 0
        while left < right:
            if left % 2:
                total += tree[left]
                left += 1
            if right % 2:
                right -= 1
                total += tree[right]
            left //= 2
            right //= 2
        return total
    def update(index, value):
        index += size
        tree[index] = value
        while index > 1:
            index //= 2
            tree[index] = tree[2 * index] + tree[2 * index + 1]
    results = []
    for operation in operations:
        if operation[0] == "sum":
            results.append(range_sum(operation[1], operation[2]))
        elif operation[0] == "update":
            update(operation[1], operation[2])
    return results
Practice

Implement segment_tree_ranges(values, operations). Operations are ["sum", left, right] with inclusive bounds or ["update", index, value]. Return one number per sum operation and do not mutate values.

Public tests

  • Verify Maintain Segment-Tree Range Sums behavior

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Segment Tree or Fenwick Tree

Choose a segment tree when the combine is an arbitrary associative operation or the problem needs richer range updates. Choose a Fenwick tree for compact point-update and prefix-sum workflows. With immutable data, a prefix array is usually simpler than either structure.

Explain It in an Interview

Say: “Each node caches the aggregate for an explicit range. A query decomposes its target into disjoint cached ranges; a point update repairs exactly one root path.” Name the combine and identity, state O(n) build, O(log n) query/update, and O(n) space. The Python list reference(opens in a new tab) covers the array representation.

Maintain Segment-Tree Range Sums(opens in a new tab) turns both query and update invariants into an executable trace.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Segment Tree itself is taught as an interview abstraction.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Core Segment Tree workflowO(n + m log n)O(n + m log n)Use a 2n iterative segment tree, a half-open boundary walk for sums, and ancestor recomputation for updates.

Space

O(n) for the demonstrated Segment Tree workflow.

Assumptions

  • Tree indexing provides logarithmic updates and prefix or interval queries after linear construction.
  • The bound counts the operations in Maintain Segment-Tree Range Sums and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

  1. State the precise Segment Tree invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Store segment aggregates in a flat iterative tree. This remains true after every accepted operation.
  3. Query inclusive ranges and propagate point updates to ancestors. This remains true after every accepted operation.

When To Use Or Avoid Segment Tree

Use It When

  • Use Segment Tree when its representation directly supports the prompt's repeated query or update.
  • Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

  • Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
  • Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Segment Tree invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def segment_tree_ranges(values, operations):
    pass

Use instead

def segment_tree_ranges(values, operations):
    size = len(values)
    tree = [0] * (2 * size)
    tree[size:] = values
    for index in range(size - 1, 0, -1):
        tree[index] = tree[2 * index] + tree[2 * index + 1]
    def range_sum(left, right):
        left += size
        right += size + 1
        total = 0
        while left < right:
            if left % 2:
                total += tree[left]
                left += 1
            if right % 2:
                right -= 1
                total += tree[right]
            left //= 2
            right //= 2
        return total
    def update(index, value):
        index += size
        tree[index] = value
        while index > 1:
            index //= 2
            tree[index] = tree[2 * index] + tree[2 * index + 1]
    results = []
    for operation in operations:
        if operation[0] == "sum":
            results.append(range_sum(operation[1], operation[2]))
        elif operation[0] == "update":
            update(operation[1], operation[2])
    return results

Where you will hit this: Maintain Segment-Tree Range Sums(opens in a new tab)

Breaking the central invariant

Updates the leaf but never recomputes ancestors, so a later range query returns a stale aggregate.

Prevent it: Keep this invariant visible while editing: State the precise Segment Tree invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def segment_tree_ranges(values, operations):
    data = list(values)
    results = []
    for operation in operations:
        if operation[0] == "sum":
            results.append(sum(data[operation[1]:operation[2] + 1]))
        elif operation[0] == "update":
            pass
    return results

Use instead

def segment_tree_ranges(values, operations):
    size = len(values)
    tree = [0] * (2 * size)
    tree[size:] = values
    for index in range(size - 1, 0, -1):
        tree[index] = tree[2 * index] + tree[2 * index + 1]
    def range_sum(left, right):
        left += size
        right += size + 1
        total = 0
        while left < right:
            if left % 2:
                total += tree[left]
                left += 1
            if right % 2:
                right -= 1
                total += tree[right]
            left //= 2
            right //= 2
        return total
    def update(index, value):
        index += size
        tree[index] = value
        while index > 1:
            index //= 2
            tree[index] = tree[2 * index] + tree[2 * index + 1]
    results = []
    for operation in operations:
        if operation[0] == "sum":
            results.append(range_sum(operation[1], operation[2]))
        elif operation[0] == "update":
            update(operation[1], operation[2])
    return results

Where you will hit this: Maintain Segment-Tree Range Sums(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(n + m log n).

Avoid

def segment_tree_ranges(values, operations):
    data = list(values)
    results = []
    for operation in operations:
        if operation[0] == "sum":
            results.append(sum(data[operation[1]:operation[2] + 1]))
        elif operation[0] == "update":
            pass
    return results

Use instead

def segment_tree_ranges(values, operations):
    size = len(values)
    tree = [0] * (2 * size)
    tree[size:] = values
    for index in range(size - 1, 0, -1):
        tree[index] = tree[2 * index] + tree[2 * index + 1]
    def range_sum(left, right):
        left += size
        right += size + 1
        total = 0
        while left < right:
            if left % 2:
                total += tree[left]
                left += 1
            if right % 2:
                right -= 1
                total += tree[right]
            left //= 2
            right //= 2
        return total
    def update(index, value):
        index += size
        tree[index] = value
        while index > 1:
            index //= 2
            tree[index] = tree[2 * index] + tree[2 * index + 1]
    results = []
    for operation in operations:
        if operation[0] == "sum":
            results.append(range_sum(operation[1], operation[2]))
        elif operation[0] == "update":
            update(operation[1], operation[2])
    return results

Where you will hit this: K-Radius Subarray Averages(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.