Skip to content
Hello Python

Maintain Segment-Tree Range Sums

Practice ExerciseAdvancedHardArraySegment Tree

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

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.

Starter code

def segment_tree_ranges(values, operations):
    pass
Test cases

range-and-update

{
  "args": [
    [
      2,
      1,
      5,
      3
    ],
    [
      [
        "sum",
        1,
        3
      ],
      [
        "update",
        2,
        4
      ],
      [
        "sum",
        0,
        2
      ]
    ]
  ]
}

Expected: [9,7]

single-value

{
  "args": [
    [
      8
    ],
    [
      [
        "sum",
        0,
        0
      ],
      [
        "update",
        0,
        -2
      ],
      [
        "sum",
        0,
        0
      ]
    ]
  ]
}

Expected: [8,-2]

Wizard outline
  1. Step 1: Build the segment tree

    Place values in leaf slots and compute every parent sum bottom-up. A correct root sum proves the compact two-level indexing layout before range logic.

  2. Step 2: Query an inclusive range

    Translate inclusive bounds to leaf indexes and consume the half-open interval inward. The iterative two-pointer walk selects only nodes fully covered by the requested range.

  3. Step 3: Propagate a point update

    Replace one leaf value and recompute each ancestor until the root. Updating ancestors keeps future range queries consistent without rebuilding the tree.

Footguns and prerequisites
  • Mixing inclusive input bounds with a half-open internal query drops the right endpoint.
  • Updating a leaf without rebuilding its ancestors leaves future sums stale.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Use a 2n iterative segment tree, a half-open boundary walk for sums, and ancestor recomputation for updates.

Why it works: Every internal node stores the sum of its leaf interval. A range query partitions the requested interval into disjoint stored segments, and an update repairs exactly the ancestors whose interval contains the changed point.

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