0Pricing
Coding Interview Prep · Lesson

Segment Tree: Build & Query

Range min, max, or sum in log n.

Segment Tree: Build & Query is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

Beyond the Fenwick Tree

A Fenwick tree shines for sums, but a segment tree handles min, max, gcd, and more. It is the flexible workhorse of range queries.

A Tree Over Ranges

Each node owns a range of the array. The root covers everything; children split it in half until leaves hold single elements.

Array-Backed Storage

We store the tree in a flat array of size 2n or 4n. Node 1 is the root; children of node i sit at 2i and 2i+1.

seg = [0] * (2 * n)

Leaves Hold the Data

In the iterative form, the original values live in the second half of the array, at indices n through 2n-1.

for i in range(n):
    seg[n + i] = a[i]

Build From the Bottom Up

Each internal node is the combine of its two children. Fill them from n-1 down to 1, and the whole tree is ready.

for i in range(n - 1, 0, -1):
    seg[i] = seg[2*i] + seg[2*i+1]

The Combine Operation

The combine function defines the tree. Use plus for sums, min for minimums, or max for maximums. Swap it to change the query.

def combine(x, y):
    return min(x, y)

Point Update, Then Climb

To change one value, set the leaf and walk up to the root, recomputing each parent from its two children along the way.

i += n
seg[i] = value
while i > 1:
    i //= 2
    seg[i] = combine(seg[2*i], seg[2*i+1])

Query a Half-Open Range

Range queries scan from both ends, folding boundary nodes into the answer. The interval is half-open, covering l up to but not r.

The Iterative Query Loop

Move l and r toward each other. When an index is an odd boundary, absorb that node before stepping the pointer.

while l < r:
    if l & 1: res = combine(res, seg[l]); l += 1
    if r & 1: r -= 1; res = combine(res, seg[r])
    l //= 2; r //= 2

Logarithmic on Both Ends

Build is O(n), while each update and query is O(log n). That balance is what makes segment trees so versatile.

Mind the Identity Element

Start your result at the operation's identity: 0 for sum, infinity for min, negative infinity for max. The wrong start gives wrong answers.

res = float('inf')

Quick Check

Where does the raw data live in the iterative tree?

Recap: Flexible Ranges

You built a segment tree: leaves in the second half, parents as combines, with O(log n) updates and queries for sum, min, or max. 🌳

Frequently asked questions

Is the “Segment Tree: Build & Query” lesson free?

Yes — the full text of “Segment Tree: Build & Query” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Segment Tree: Build & Query”?

Range min, max, or sum in log n. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Coding Interview Prep?

No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Segment Tree: Build & Query” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Coding Interview Prep lesson?

Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

  1. Fenwick Tree for Prefix Sums
  2. Inversions with a BIT
  3. Segment Tree: Build & Query
  4. Lazy Propagation for Range Updates
← Back to Coding Interview Prep