Parity-Based Segment Updates

Parity updates (flip odd/even, toggle 0/1) often use XOR lazy or a segment tree storing counts of ones.

Why this shows up in the real world

Time-series dashboards, game leaderboards, and competitive programming interval problems all need fast answers on changing arrays.

Core idea (explained for students)

Combine lazy flip with sum/count query—two flips cancel (XOR lazy parity).

Try this in Python

def flip_range(arr: list[int], l: int, r: int) -> None:
    for i in range(l, r + 1):
        arr[i] ^= 1


a = [1, 0, 1, 0]
flip_range(a, 1, 2)
print(a)

Common mistakes

• Storing only sum without count when need distinct parity classes.
• Mod 2 arithmetic confusion.

Key takeaways

• XOR lazy on 0/1 array for range flip.
• Query “number of ones” = range sum after flip lazy.