ArepitaDePernil's blog

Is there a way to solve maximum-submatrix-sum problem with segment trees?
By ArepitaDePernil, 10 years ago, In English

Hello i have been thinking on this question for quite a while, but i can't find the answer. As i have read in many forums it is possible to solve the maximum-subarray-sum problem (usually solved by Kadane's algorithm) using Segment Trees, then obviously the question came by, is it possible to solve the maximum-submatrix-sum problem using Segment Trees? , i think it should be faster than the O(N^3) adapted Kadane's algorithm.

:) just a question trying to learn more

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I doubt there is something better than O(N^3).

I can't think of a clever way to use segment trees since after all in the maximum-submatrix-sum problem you don't have any updates. So sum of a subrmatrix can be found in O(1) after preprocessing, so I can't see how segment trees can help.

But who knows, there might be some crazy O(N^2 log^2 N) solution.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Well, probably you meant N^2 log^2 N.

    At least you need to read all the matrix:)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, fixed it, of course I meant O(N^2 log^2 N) :D

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did some extensive searching on this topic before and didn't find anything interesting. You can more or less safely assume that no better approach is known in general case, while some improvements can be made for particular cases (like small integers for matrix entries or such); alas, I don't have any links for this.

→ Reply