# 2D segment tree query time complexity

These sources cp-algorithms and geeksforgeeks state that query complexity (for example, submatrix sum) of 2-D segment tree is O(logN * logM), because

it first descends the tree in the first coordinate, and for each traversed vertex of that tree, it makes a query from the usual tree of segments along the second coordinate

However, in all implementations I have met, a query descends the tree along the second coordinate only when it reaches some node of the first tree (cannot recurse any further). Next, since there are no more than 4 recursive calls per level of a segment tree during a query, there would be no more than 4 queries along the second coordinate in total. So, in my view, the rime complexity should be O(logN + logM). What do I miss?

• What do you mean by 4 recursive calls per level? The number of levels is log M so you need, for each row in question, to do log M work, no? Dec 4 '21 at 9:13
• cp-algorithms.com/data_structures/segment_tree.html contains a proof that during a query at each level no more than four vertices is visited Dec 4 '21 at 9:24
• I think in your case I would implement the algorithm you have in mind and try to prove the running time you believe is right. Either you have a proof, or you reach an insight. Dec 4 '21 at 10:03