Is a log(n) solution?


  • -1
    A

    I tried to use a 2-d segment tree. It can pass the test and the update can be done in O(logn). However the worst case time complexity for "get_sum" will much more than O(logn) (where n is the one dimension size of the matrix) the checked node at bottom level can go up to O(n). (in the 1-d segment tree, we have O(1) at each level). We can solve this question in O(n) time as shown on the other post. I just want to know if there is a O(logn) solution.


  • 0

    The time complexity of a 2D segment tree (instead of a quad-tree) should be O(logn * logm).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.