Data Structures19 sections · 729 units
Open in Course

2D Segment Tree Solution

Implement your solution

For this problem size (200×200200 \times 200), 2D BIT is simpler and sufficient. But you'll understand the 2D segment tree approach:

# Build outer segment tree
for outer_node:
    # Build inner segment tree at this node
    for inner_node:
        if leaf:
            tree2D[outer][inner] = matrix[row][col]
        else:
            combine children

Query descends both dimensions:

def query2D(outer, r1, r2, c1, c2):
 # If row range outside: return 0
 # If row range inside: query inner tree for [c1, c2]
 # Else: recurse on both children, sum results

For competitive programming, 2D BIT is usually preferred for its simpler implementation.