#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/common-segment-tree-bugs

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/segment-trees/common-segment-tree-bugs

Repovive

Common Segment Tree Bugs - Segment Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Common Segment Tree Bugs

Debugging tips

Bug 1: Wrong tree size

# Wrong - may overflow for non-power-of-2
tree = [0] * (2 * n)

# Correct - safe for all sizes
tree = [0] * (4 * n)

Bug 2: Range boundaries in query

# Check order: (segment outside query) then (segment inside query)
if r < start or end < l:
    return identity
if l <= start and end <= r:
    return tree[node]

Bug 3: Forgetting pushDown in lazy propagation Call pushDown BEFORE recursing to children, in both query and update.

Bug 4: Identity element wrong

Sum: 0
Min: +infinity
Max: -infinity
Product: 1

Test with: single element, entire range query, point vs range update.