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 much harder to implement.