For 2D range queries on a matrix, build a "segment tree of segment trees": - Outer tree: segments along rows - Each outer node contains: an inner segment tree along columns Query :
Query outer tree for row range
At each outer node, query the inner tree for column range tree2D[outer_node][inner_node] Time complexity: - Build: - Query: - Point update: Space: for the nested structure. 2D range updates with lazy propagation are significantly more complex.