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?

  • $\begingroup$ 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? $\endgroup$
    – Pål GD
    Dec 4 '21 at 9:13
  • $\begingroup$ 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 $\endgroup$ Dec 4 '21 at 9:24
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Dec 4 '21 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.