2D Segment Tree


(Team) #1

Segment Tree is used to answer range queries in an array. The data structure can be extended to 2 dimensions to answer sub-matrix queries in logarithmic time. Some examples of these queries are :

  • Maximum/minimum element in sub-matrix
  • Sum of elements in sub-matrix
  • XOR of elements is sub-matrix

Read this article to understand 2D Segment Tree in depth

Have a doubt or thought? Join the discussion now
This is a companion discussion topic for the original entry at http://iq.opengenus.org/2d-segment-tree/