Range Queries

Segment Trees & Range Queries

Perform dynamic point updates and range queries (Sum, Min, Max) in strictly O(log n) time. Perfect for arrays that change frequently.

Why Segment Trees?

If an array is static, Prefix Sums handle range sums in O(1). But if elements update, Prefix Sums take O(n) to rebuild. Segment Trees do both in O(log n).

Tree Structure
A binary tree where each node represents a segment (range) of the array. The root represents [0, n-1]. Leaves represent single elements.
Array Representation
Like a heap, represented as a 1D array of size 4N. Left child of idx is 2*idx + 1, right is 2*idx + 2.

Time Complexity: Build: O(n), Query: O(log n), Update: O(log n).

Query Logic (Divide & Conquer)

Complete Overlap
If the node's range is completely inside the query range, return the node's value immediately.
No Overlap
If the node's range is completely outside the query range, return a neutral value (0 for sum, infinity for min).
Partial Overlap
Query both left and right children and merge their results.

Segment Tree (Sum Query + Point Update)

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.build(data, 0, 0, self.n - 1)
        
    def build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        left_child, right_child = 2 * node + 1, 2 * node + 2
        self.build(data, left_child, start, mid)
        self.build(data, right_child, mid + 1, end)
        self.tree[node] = self.tree[left_child] + self.tree[right_child]
        
    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        left_child, right_child = 2 * node + 1, 2 * node + 2
        if start <= idx <= mid:
            self.update(left_child, start, mid, idx, val)
        else:
            self.update(right_child, mid + 1, end, idx, val)
        self.tree[node] = self.tree[left_child] + self.tree[right_child]
        
    def query(self, node, start, end, l, r):
        if r < start or end < l:  # No overlap
            return 0
        if l <= start and end <= r:  # Complete overlap
            return self.tree[node]
        # Partial overlap
        mid = (start + end) // 2
        left_child, right_child = 2 * node + 1, 2 * node + 2
        p1 = self.query(left_child, start, mid, l, r)
        p2 = self.query(right_child, mid + 1, end, l, r)
        return p1 + p2

LeetCode Problems

  • MediumRange Sum Query - MutableStandard Segment Tree / BIT
  • HardCount of Smaller Numbers After SelfSegment tree on values / Merge Sort
  • HardReverse PairsSegment tree on values / Merge Sort
  • HardFalling SquaresSegment Tree with Lazy Propagation