Segment Tree

Segment Tree | Algoryva

First, the naive way

Scan the range each time

For a range minimum, the direct way scans the range. A point update is trivially O(1): overwrite the value.

But every query costs the length of the range, up to n. With 2 × 10⁵ queries on an array of 2 × 10⁵ values that is up to 4 × 10¹⁰ steps. Prefix sums do not help, because a minimum cannot be subtracted out, and the Fenwick tree only supports undoable operations.

python

a = [5, 2, 6, 1, 7, 3, 8, 4]

def range_min_naive(a, l, r):          # positions l..r inclusive
    best = a[l]
    for i in range(l + 1, r + 1):
        if a[i] < best:
            best = a[i]
    return best

print(range_min_naive(a, 2, 6))   # 1
a[3] = 9                               # a point update is O(1) ...
print(range_min_naive(a, 2, 6))   # 3
# ... but every query still scans the whole range: O(n)

Cost: O(n) per query, so O(n × q) overall.

Worked by hand

The same query by hand

Array [5, 2, 6, 1, 7, 3, 8, 4] (positions 0 to 7), query: minimum of positions 2 to 6.

node (range)	relation to 2..6	action
0-7	partly overlaps	open it
0-3	partly overlaps	open it
0-1	outside	ignore
2-3	inside	take min(6, 1) = 1
4-7	partly overlaps	open it
4-5	inside	take min(7, 3) = 3
6-7	partly overlaps	open it
6-6	inside	take 8
7-7	outside	ignore

1
Combine the taken pieces
The answer is min(1, 3, 8) = 1, built from three stored values instead of scanning five elements.
2
Why it stays fast
At each level at most two nodes are only partly covered (the ones at the two ends of the range). Everything else is either fully inside or fully outside, so the work per level is constant.

Implementation

A segment tree for any associative operation

One class handles minimum, maximum, sum or gcd: pass the operation and its identity.

Plan in plain steps

pseudocode

build: copy values into the leaves; for i from n − 1 down to 1: t[i] = op(t[2i], t[2i + 1])
update(i, v): set the leaf; walk up recomputing each parent
query(l, r): move two ends up the tree, taking a node whenever an end is a right child

python

INF = float("inf")

class SegTree:
    def __init__(self, a, op=min, identity=INF):
        self.n = len(a)
        self.op = op
        self.identity = identity
        self.t = [identity] * self.n + list(a)      # leaves live at t[n .. 2n - 1]
        for i in range(self.n - 1, 0, -1):
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, v):                         # set position i (0-indexed) to v
        i += self.n
        self.t[i] = v
        while i > 1:
            i //= 2
            self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l, r):                          # half-open range [l, r)
        res = self.identity
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res = self.op(res, self.t[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.op(res, self.t[r])
            l //= 2
            r //= 2
        return res

a = [5, , , , , , , ]
st = (a)
(st.(, ))   
st.(, )
(st.(, ))   
(st.(, ), st.(, ))   
total = (a,  x, y: x + y, )
(total.(, ))   
(total.(, ))

Reading the code

›self.t[i] = op(self.t[2 * i], self.t[2 * i + 1]) is the only combining rule: every ancestor is the combination of its two children.
›In query, the checks l & 1 and r & 1 ask “is this end a right child?”. A right child on the left edge must be taken now and the edge moved right (l += 1); an exclusive right end that is odd means the node just before it belongs to the range (r -= 1).
›query(2, 7) is the minimum of positions 2 to 6 (half-open), as in the animation: 1. After update(3, 9) the minimum becomes 3.
›With op = lambda x, y: x + y and identity 0 the same class sums: total 36. An empty range query(3, 3) returns the identity, 0.
›This compact version needs a commutative operation (order does not matter) such as min, max, sum or gcd. For non-commutative operations keep separate left and right accumulators.

Implementation

Check it against brute force

A data structure with index arithmetic is easy to get subtly wrong. The same class below is checked on 300 random arrays with 25 random updates and queries each against the obvious min(a[l:r]).

python

import random

INF = float("inf")

class SegTree:
    def __init__(self, a, op=min, identity=INF):
        self.n, self.op, self.identity = len(a), op, identity
        self.t = [identity] * self.n + list(a)
        for i in range(self.n - 1, 0, -1):
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, v):
        i += self.n
        self.t[i] = v
        while i > 1:
            i //= 2
            self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l, r):
        res = self.identity
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res = self.op(res, self.t[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.op(res, self.t[r])
            l //= 2
            r //= 2
        return res

random.seed(11)
ok = True
for _ in range(300):
    n = random.randint(1, 13)
    a = [random.randint(-20, 20) for _ in range(n)]
    st = SegTree(a)
    for _ in range(25):
        if random.random() < 0.4:
            i, v = random.randrange(n), random.randint(-20, 20)
            a[i] = v
            st.update(i, v)
        else:
            l = random.randrange(n)
            r = random.randint(l + 1, n)
            ok = ok and st.query(l, r) == min(a[l:r])
print(ok)   # True

Reading the code

›Random array sizes from 1 to 13 include non-powers of two, which is where bottom-up segment trees often break.
›Each step either updates a random position or queries a random half-open range, and compares with a plain slice minimum.
›Printing True means all comparisons agreed. Doing this before relying on a structure in a contest is cheap insurance.

Implementation

Range updates with lazy propagation

Now suppose an update adds a value to every element of a range and queries ask for range sums. Updating each element would be O(n). Instead, when a node's range lies completely inside the update, add to its sum and leave a lazy tag (“this much is still owed to my children”) rather than descending. The tag is pushed down only when a later operation needs to look inside.

python

import random

class RangeAddSum:
    def __init__(self, a):
        self.n = len(a)
        self.sum = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)         # pending "add v to everything below" tags
        self._build(1, 0, self.n - 1, a)

    def _build(self, x, l, r, a):
        if l == r:
            self.sum[x] = a[l]
            return
        m = (l + r) // 2
        self._build(2 * x, l, m, a)
        self._build(2 * x + 1, m + 1, r, a)
        self.sum[x] = self.sum[2 * x] + self.sum[2 * x + 1]

    def _push(self, x, l, r):                   # hand the pending tag down to both children
        if self.lazy[x]:
            m = (l + r) // 2
            for child, cl, cr in ((2 * x, l, m), (2 * x + 1, m + 1, r)):
                self.sum[child] += self.lazy[x] * (cr - cl + 1)
                self.lazy[child] += self.lazy[x]
            self.lazy[x] = 0

    def add(self, ql, qr, v, x=1, l=0, r=):
         r  :
            r = self.n - 
         qr < l  r < ql:
            
         ql <= l  r <= qr:                 
            self.sum[x] += v * (r - l + )
            self.lazy[x] += v
            
        self.(x, l, r)
        m = (l + r) // 
        self.(ql, qr, v,  * x, l, m)
        self.(ql, qr, v,  * x + , m + , r)
        self.sum[x] = self.sum[ * x] + self.sum[ * x + ]

     (self, ql, qr, x=, l=, r=):
         r  :
            r = self.n - 
         qr < l  r < ql:
             
         ql <= l  r <= qr:
             self.sum[x]
        self.(x, l, r)
        m = (l + r) // 
         self.(ql, qr,  * x, l, m) + self.(ql, qr,  * x + , m + , r)

st = ([, , , , ])
st.(, , )
(st.(, ))   
(st.(, ))   

random.()
ok = 
 _  ():
    n = random.(, )
    a = [random.(-, )  _  (n)]
    tree = (a)
     _  ():
        l = random.(n)
        r = random.(l, n - )
         random.() < :
            v = random.(-, )
            tree.(l, r, v)
             i  (l, r + ):
                a[i] += v
        :
            ok = ok  tree.(l, r) == (a[l:r + ])
(ok)

Reading the code

›add on a fully covered node does sum += v × length and lazy += v, then stops. That is what keeps range updates at O(log n).
›_push hands the pending tag to both children (updating their sums and tags) and clears it. It must be called before descending, in both add and query; forgetting it is the classic bug.
›After the children are updated, the parent's sum is recomputed from them.
›The example adds 10 to positions 1 to 3 of [1, 2, 3, 4, 5]: the total becomes 15 + 30 = 45 and position 2 becomes 13. The final loop checks 200 random arrays with random range adds and range sums against a plain list.

Implementation

Descending the tree: first position at least x

A segment tree can also *search*. With a maximum tree, “the first position whose value is at least x” is found by walking down from the root: go left if the left child's maximum is at least x, otherwise right. This needs the size padded to a power of two so the layout is a perfect tree.

python

NEG = float("-inf")

def build_max(a):
    size = 1
    while size < len(a):
        size *= 2
    t = [NEG] * (2 * size)
    for i, v in enumerate(a):
        t[size + i] = v
    for i in range(size - 1, 0, -1):
        t[i] = max(t[2 * i], t[2 * i + 1])
    return t, size

def first_at_least(t, size, x):
    if t[1] < x:
        return -1
    i = 1
    while i < size:
        i = 2 * i if t[2 * i] >= x else 2 * i + 1
    return i - size

t, size = build_max([3, 1, 4, 1, 5, 9, 2, 6])
print(first_at_least(t, size, 5))   # 4
print(first_at_least(t, size, 7))   # 5
print(first_at_least(t, size, 10))   # -1
print(first_at_least(*build_max([2, 8, 8, 1, 4]), 8))   # 1

Reading the code

›t[1] < x means even the overall maximum is too small: return -1.
›Each step compares the left child's maximum with x. If it is large enough, the answer is somewhere inside it (and it is the *first*, since it is left of everything else); otherwise go right.
›After log₂ size steps i is a leaf; i − size is the array position. In [3, 1, 4, 1, 5, 9, 2, 6] the first value at least 5 is at position 4 and at least 7 is at position 5.
›The last call shows ties: in [2, 8, 8, 1, 4] the first 8 is at position 1.

Worked problem

Tallest building in a changing skyline

The problem

Buildings stand in a row with given heights. Process events in order: set i h changes the height of building i to h; max l r asks for the tallest building among positions l to r (inclusive). Print the answer to each max event.

The data changes, and the question is a maximum, which a Fenwick tree cannot answer. A segment tree with op = max and identity -inf fits.
A set becomes update(i, h).
An inclusive max l r becomes query(l, r + 1) in the half-open convention.

python

INF = float("inf")

class SegTree:
    def __init__(self, a, op=max, identity=-INF):
        self.n, self.op, self.identity = len(a), op, identity
        self.t = [identity] * self.n + list(a)
        for i in range(self.n - 1, 0, -1):
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, v):
        i += self.n
        self.t[i] = v
        while i > 1:
            i //= 2
            self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])

    def query(self, l, r):
        res = self.identity
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res = self.op(res, self.t[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.op(res, self.t[r])
            l //= 2
            r //= 2
        return res

def tallest_so_far(heights, events):
    st = SegTree(heights)
    out = []
    for kind, x, y in events:
        if kind == "set":
            st.update(x, y)
        else:
            out.append(st.query(x, y + 1))
    return out

events = [("max", 0, 4), ("set", 2, 50), ("max", 0, 4), ("max", 3, 4), ("set", 2, 1), ("max", 1, 3)]
print(tallest_so_far([4, 9, 2, 7, 5], events))   # [9, 50, 7, 9]

Takeaway. The same class from the lesson became a different tool by changing two arguments (op and identity). After setting position 2 to 50 the tallest is 50, and after setting it back to 1 the range 1 to 3 has maximum 9.

Worked problem

First building at least this tall

The problem

Given heights and a threshold x, find the leftmost building whose height is at least x, in O(log n) per query (without scanning).

Build a maximum tree padded to a power of two.
If the root's maximum is below x, nobody qualifies.
Otherwise walk down: if the left child's maximum is at least x, the leftmost qualifying building is in it; otherwise it is in the right child.
The leaf reached is the answer.

python

NEG = float("-inf")

def build_max(a):
    size = 1
    while size < len(a):
        size *= 2
    t = [NEG] * (2 * size)
    for i, v in enumerate(a):
        t[size + i] = v
    for i in range(size - 1, 0, -1):
        t[i] = max(t[2 * i], t[2 * i + 1])
    return t, size

def first_at_least(t, size, x):
    if t[1] < x:
        return -1
    i = 1
    while i < size:
        i = 2 * i if t[2 * i] >= x else 2 * i + 1
    return i - size

t, size = build_max([3, 1, 4, 1, 5, 9, 2, 6])
print(first_at_least(t, size, 5))   # 4
print(first_at_least(t, size, 7))   # 5
print(first_at_least(t, size, 10))   # -1
print(first_at_least(*build_max([2, 8, 8, 1, 4]), 8))   # 1

Takeaway. A segment tree is a search structure as well as a query structure: the stored maxima tell you, at every node, which half can contain the answer. It is the same “discard half” idea as binary search, performed on a tree.

Wrap-up

Remember this

A segment tree stores the answer for every block of a recursive halving of the array, so any range is a few ready-made blocks.
It supports any associative operation (min, max, sum, gcd), unlike a Fenwick tree, with O(log n) updates and queries.
The compact bottom-up version needs only a flat array of 2n cells and a few lines of code.
Lazy propagation postpones range updates with pending tags, giving O(log n) range add and range sum.
Pick the simplest tool that fits: prefix sums, sparse table, Fenwick tree, then segment tree.

Cheat sheet

Layout: leaves at t[n..2n−1]; parent i//2; children 2i, 2i+1
Update: set leaf; while i > 1: i //= 2; t[i] = op(t[2i], t[2i+1])
Query [l, r): l += n; r += n; while l < r: take t[l] if l odd; take t[r−1] if r odd; l //= 2; r //= 2
Identities: min: inf · max: −inf · sum/xor: 0 · product: 1
Cost: build O(n) · update, query O(log n) · lazy range update O(log n)
Lazy: tag a fully covered node; push tags down before opening it

Top traps to avoid

Using the wrong identity element.
Mixing inclusive and half-open ranges.
Forgetting to recompute parents after an update.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What does each node of a segment tree store?
2.What is the cost of one range query on a segment tree of n values?
3.For [5, 2, 6, 1, 7, 3, 8, 4], what is the minimum over positions 2 to 6?
4.Why can a segment tree answer range minimum while a Fenwick tree cannot?
5.“Add 5 to every element from l to r, then report the sum of a range” suggests:
6.What goes wrong in a lazy segment tree if you forget to push the tag down before opening a node?
7.Iterative segment tree for a = [1, 2, 3, 4] built with sums. What does the range query [1, 3) return (sum of a[1] and a[2])?
8.Same tree. Set a[0] = 10 (a point update), then query the whole range [0, 4). What is printed?
9.Range-minimum segment tree over a = [5, 2, 8, 1, 9]: what is the minimum over indices [0, 3)?
10.What is the sum of a[2:5] for a = [1, 2, 3, 4, 5, 6]?
11.Building a segment tree from n values takes how long, and a range query takes how long?
12.What does lazy propagation add to a segment tree?
13.Which structure handles range-minimum queries directly, with point updates?
14.What is the memory used by a segment tree over n values?
15.Why can a segment tree answer min queries but a basic Fenwick tree cannot?

Segment Tree

After this lesson you will be able to

Builds on

Unlocks

A tournament bracket

Scan the range each time

Any range is a few ready-made blocks

Anatomy of a segment tree

Answering a range-minimum query

A point update touches one path

The same query by hand

A segment tree for any associative operation

Reading the code

Check it against brute force

Reading the code

Range updates with lazy propagation

Reading the code

Descending the tree: first position at least x

Reading the code

Costs and choosing a structure

Edge cases

Mistakes to avoid

How to spot a segment-tree problem

Tallest building in a changing skyline

First building at least this tall

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core1 problem

Challenge1 problem