Data Structures19 sections · 729 units
Open in Course

2D Segment Trees

Extending to matrices

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 (r1,c1,r2,c2)(r_1, c_1, r_2, c_2):

1.1. Query outer tree for row range [r1,r2][r_1, r_2]

2.2. At each outer node, query the inner tree for column range [c1,c2][c_1, c_2] tree2D[outer_node][inner_node] Time complexity:

  • Build: O(nm)O(nm)
  • Query: O(log⁡n⋅log⁡m)O(\log n \cdot \log m)
  • Point update: O(log⁡n⋅log⁡m)O(\log n \cdot \log m) Space: O(nm)O(nm) for the nested structure. 2D range updates with lazy propagation are much harder to implement.