A segment tree is a binary tree that works efficiently with ranges in an array. Think of dividing a ruler into smaller segments: the root represents the entire range, and each level breaks segments into smaller pieces. That makes it very fast to update values and calculate range queries over any part of the array. Where a plain array forces you to check every element in a range, segment trees skip large portions of the data.

Segment trees have three main operations. First, we build the tree by dividing our array into segments, where each node stores information about its range. Then we can update individual values in the array, and the tree automatically updates every segment that contains that value. Finally, we can query any range to quickly get information about that section of our array.

The efficiency is what makes segment trees worth the setup. Without one, getting the sum of a range means adding up every number in that range one at a time. With a segment tree, both updates and queries run in O(log n) time because we can skip entire sections of the array that aren't relevant to our range. That makes segment trees the right choice for problems where you need to frequently update values and calculate range information.

A segment tree divides the array into segments like chapters in a book. The root node covers the entire array range, and each level splits these ranges into halves. If we have an array of 8 elements, the root covers indices [0,7], its children cover [0,3] and [4,7], and so on until we reach single elements. Each node stores information about its segment, like the sum or minimum of all the elements in its range.

class SegmentTree:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        # Array representation: size 4n for safety
        self.tree = [0] * (4 * self.n)
        # Build the tree from input array
        if self.n > 0:
            self.build(nums, 0, 0, self.n - 1)

Even though segment trees behave like binary trees, we can store them efficiently in an array. For a node at index i, its children are at 2i + 1 and 2i + 2. The array size needs to be roughly 4n, where nis the size of the input array. That looks like a lot of space, but it's worth it for the speed we gain on every operation.

Building a segment tree starts with the input array and creates nodes that represent different ranges of it. Each leaf node holds a single element, while parent nodes store information about their range (the sum, minimum, or whatever you're tracking). We build the tree from bottom to top, combining information from smaller ranges into larger ones until we reach the root that covers the entire array.

# Build segment tree from array - O(n)
def build(self, nums: List[int], node: int, left: int, right: int) -> None:
    # Leaf node: store the array element
    if left == right:
        self.tree[node] = nums[left]
        return

    # Split range in half and build subtrees
    mid = (left + right) // 2
    left_node = 2 * node + 1
    right_node = 2 * node + 2

    self.build(nums, left_node, left, mid)
    self.build(nums, right_node, mid + 1, right)

    # Parent stores sum of children
    self.tree[node] = self.tree[left_node] + self.tree[right_node]

Building requires an array of size 4n to hold the tree, where nis the input array's length. We first copy each array element into a leaf node at the bottom of the tree, then work our way up by calculating each parent's value from its children. The whole construction takes O(n) time and leaves the tree ready for efficient range operations.

Range querying is like finding information in a book using its chapters. Starting at the root, we look for segments that overlap with our target range. When we find a segment that's completely inside our range, we use its value directly instead of checking every element. That makes queries much faster than scanning element by element: they run in O(log n) time instead of O(n).

# Range query [query_left, query_right] - O(log n)
def query(self, node: int, left: int, right: int,
          query_left: int, query_right: int) -> int:
    # Completely outside range
    if query_right < left or query_left > right:
        return 0

    # Completely inside range
    if query_left <= left and right <= query_right:
        return self.tree[node]

    # Partial overlap: check both children
    mid = (left + right) // 2
    left_node = 2 * node + 1
    right_node = 2 * node + 2

    left_sum = self.query(left_node, left, mid, query_left, query_right)
    right_sum = self.query(right_node, mid + 1, right, query_left, query_right)
    return left_sum + right_sum

The query process works by splitting our search into smaller and smaller ranges until we find segments that exactly match what we need. At each node we visit, the segment is either fully contained (use its value), completely outside (ignore it), or partially overlapping (check its children). This divide-and-conquer approach is what makes segment trees so efficient for range calculations.

Updating a segment tree is like modifying a book's table of contents when you change a page. When we modify an element in our array, we have to update not just that element, but every segment that contains it. We start by changing the leaf node that represents our target element, then bubble those changes up through all its parent nodes until we reach the root. The whole thing runs in O(log n) time because we only update one path from leaf to root.

# Point update at index - O(log n)
def update(self, node: int, left: int, right: int,
           index: int, value: int) -> None:
    # Found the leaf node
    if left == right:
        self.tree[node] = value
        return

    mid = (left + right) // 2
    left_node = 2 * node + 1
    right_node = 2 * node + 2

    # Go left or right based on index
    if index <= mid:
        self.update(left_node, left, mid, index, value)
    else:
        self.update(right_node, mid + 1, right, index, value)

    # Update parent with new children values
    self.tree[node] = self.tree[left_node] + self.tree[right_node]

The update process bubbles up through the tree, recalculating each parent's value from its children. Just like changing a page number affects every chapter summary that includes that page, modifying a single element updates every segment that contains it. The segment tree stays accurate about every range, ready for the next query.

Lazy propagation is like waiting to clean your room until right before someone visits. Instead of updating every affected node immediately, we keep track of what changes need to be made and only apply them when we actually need to look at those nodes. This is especially useful for range updates, where many nodes might need the same change. If you need to add 1 to every number in a range, you can just mark that range as needing the update instead of changing every node right away.

To pull this off, each node needs to store two things: its current value and any lazy updates waiting to be applied. When we query a node that has lazy updates pending, we first apply the updates and pass them down to its children. This "do it only when you need to" approach is much more efficient than eager updates, especially when we have lots of updates followed by queries.

Segment trees are the go-to tool for range query problems where values keep changing. Both updates and queries run in O(log n), which makes them great for dynamic data where values change frequently. Here are a few tips for using them well:

Segment trees are heavyweight, but they unlock entire classes of range query problems that other structures handle clumsily. Most of these problems are advanced, so take your time. The reward is seeing how a single tree can answer thousands of queries in O(log n) each: