A segment tree is a special binary tree that works efficiently with ranges in an array. Think of it like dividing a ruler into smaller segments - the root represents the entire range, and each level breaks segments into smaller pieces. This makes it incredibly fast to update values and calculate range queries over any part of the array. Unlike regular arrays where range calculations require checking every element, segment trees skip large portions of the data.

Segment trees support three main operations that work together to manage ranges efficiently. 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 our array, and the tree automatically updates all the segments that contain that value. Finally, we can query any range to quickly get information about that section of our array.

The real power of segment trees comes from their efficiency. Without a segment tree, getting the sum of a range would mean adding up every number in that range one by one. But 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. This makes segment trees perfect for problems where we 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. For example, 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 elements in its range.

class SegmentTree:
    def __init__(self, array: List[int]):
        # Size of segment tree array is 4xn to ensure enough space
        self.size = len(array)
        self.tree = [0] * (4 * self.size)
        
        # If we have a valid size, build the tree
        if self.size > 0:
            self.build(array, 0, 0, self.size - 1)

Although segment trees look like binary trees, we can efficiently store them in an array. For a node at index i, its children are at indices 2i + 1 and 2i + 2. The array size needs to be roughly 4n, where n is the size of our input array. This might seem like a lot of space, but it's worth it for the speed we gain in our operations.

Building a segment tree starts with our input array and creating nodes that represent different ranges of the array. Each leaf node holds a single element, while parent nodes store information about their range - like the sum or minimum of all elements they cover. We build the tree from bottom to top, combining information from smaller ranges to create larger ones until we reach the root that covers the entire array.

def build(self, array: List[int], node: int, start: int, end: int) -> None:
    # If we're at a leaf node, store the array element in the segment tree
    if start == end:
        self.tree[node] = array[start]
    else:
        # Calculate the mid point and left & right children
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # Recursively build the left & right halves
        self.build(array, left_child, start, mid)
        self.build(array, right_child, mid + 1, end)
        
        # Store the total sum of the left & right child segments
        total = self.tree[left_child] + self.tree[right_child]
        self.tree[node] = total

The building process requires an array of size 4n to store our tree, where n is the input array's length. We first copy each array element to a leaf node in the bottom level of the tree, then work our way up by calculating each parent's value from its children. This construction takes O(n) time and sets up our tree 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 can use its value directly instead of checking all its elements. This makes queries much faster than checking each element individually - running in O(log n) time instead of having to scan the entire range.

def query(self, left: int, right: int, node: int = 0, start: int = 0, end: int = None) -> int:
    # Set the default end of the segment to the last index if not specified
    if end is None:
        end = self.size - 1
    
    # If segment is completely outside the range, return 0
    if right < start or left > end:
        return 0
    # If segment is completely inside the range, return the sum for this node
    if left <= start and end <= right:
        return self.tree[node]
    
    # Segment is partially in range, find middle and left & right children
    mid = (start + end) // 2
    left_child = 2 * node + 1
    right_child = 2 * node + 2
    
    # Query both left and right halves of the segment
    left_sum = self.query(left, right, left_child, start, mid)
    right_sum = self.query(left, right, right_child, mid + 1, end)
    
    # Sum of the left and right results
    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. For each node we visit, we have three possibilities: the segment is 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 need to update not just that element, but all the segments that contain it. We start by changing the leaf node that represents our target element, then bubble up these changes through all its parent nodes until we reach the root. This process runs in O(log n) time since we only need to update one path from leaf to root.

def update(self, idx: int, value: int, node: int = 0, start: int = 0, end: int = None):
    # Set the default end of the segment to the last index if not specified
    if end is None:
        end = self.size - 1
    
    # If the index to update is found
    if start == end:
        self.tree[node] = value
    else:
        # Calculate the midpoint and left & right children
        mid = (start + end) // 2
        left_child = 2 * node + 1
        right_child = 2 * node + 2
        
        # Update the correct half depending on index location
        if idx <= mid:
            self.update(idx, value, left_child, start, mid)
        else:
            self.update(idx, value, right_child, mid + 1, end)
        
        # Recompute the current node's sum after the update
        total = self.tree[left_child] + self.tree[right_child]
        self.tree[node] = total

The update process bubbles up through the tree, recalculating each parent's value based on its children. Just like how changing a page number affects all chapter summaries that include that page, modifying a single element updates every segment that contains it. This ensures our segment tree is always accurate about every range, ready for the next query.

Lazy propagation is like waiting to clean your room until just before someone visits. Instead of updating all affected nodes 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. For example, if we need to add 1 to every number in a range, we can just mark that range as needing the update rather than changing every node right away.

To make this work, each node in our tree needs to store two things: its current value and any lazy updates. 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 makes our segment tree much more efficient, especially when we have lots of updates followed by queries.

Segment trees should be your go-to tool for solving range query problems efficiently in coding interviews. They allow rapid updates and queries, making them great for dynamic data where values change frequently. Here are some essential tips and tricks to master segment trees: