Algorithm Guidecomplexity: Query/Update O(log n)

Segment Tree

A tree for quickly computing range sums, minimums, and the like. Each node owns one interval, handling both point updates and range queries in O(log n) — covering the update weakness of a prefix-sum array.

01Segment Tree

Explore How It Works

Segment tree. Over the array [1, 3, 5, 7], each node holds the sum of its own interval.

Leaves are the elements themselves, and each parent is the sum of its two children. Merging upward, the root becomes the total sum 16.

query(1, 3) · compute the sum of indices 1 to 3. Start descending from the root [0,3].

The left [0,1] only partially overlaps the query. Descend further and adopt just [1,1]=3.

The right [2,3] is fully contained in the query. Adopt all of 12 without descending further.

Combine the adopted pieces · 3 + 12 = 15. We got the range sum in O(log n) without adding up every leaf.

Live Python

1def query(node, node_lo, node_hi, lo, hi):

2 if hi < node_lo or node_hi < lo:

3 return 0 # no overlap

4 if lo <= node_lo and node_hi <= hi:

5 return tree[node] # fully contained → whole

6 mid = (node_lo + node_hi) // 2

7 left = query(2*node, node_lo, mid, lo, hi)

8 right = query(2*node+1, mid + 1, node_hi, lo, hi)

9 return left + right # combine partial sums

1 / 6

02 Understand It Simply

For Everyone

🔑How It Works

Halves the range recursively and stores each range's sum at its node, answering range sums and point updates both in O(log n).

💡In Plain Words

A tree where each node holds the sum (or minimum) of a certain interval.

Whether one value changes or you ask for a wide range's sum, it answers in O(log n).

📍Where It's Used

–Range sum/minimum queries
–live rankings and stats
–game scoreboards

03 Python Implementation

A clean, readable reference implementation of the core logic of Segment Tree.

core_implementation.py

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2*i] + self.tree[2*i + 1]

    def query(self, l, r):   # range sum [l, r)
        res = 0
        l += self.n; r += self.n
        while l < r:
            if l & 1:
                res += self.tree[l]; l += 1
            if r & 1:
                r -= 1; res += self.tree[r]
            l >>= 1; r >>= 1
        return res

04 Frequently Asked Questions

FAQ

What is Segment Tree?+

What is the time complexity of Segment Tree?+

The time complexity of Segment Tree is Query/Update O(log n). Follow the step-by-step visualization to see exactly why.

Where is Segment Tree used?+

Range sum/minimum queries, live rankings and stats, game scoreboards.

What's a simple analogy for Segment Tree?+

Halves the range recursively and stores each range's sum at its node, answering range sums and point updates both in O(log n).

→ Trees — see allRelated