{"id":348,"date":"2017-09-18T22:14:44","date_gmt":"2017-09-19T05:14:44","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=348"},"modified":"2018-07-10T18:26:09","modified_gmt":"2018-07-11T01:26:09","slug":"leetcode-304-range-sum-query-2d-immutable","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-304-range-sum-query-2d-immutable\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 304. Range Sum Query 2D &#8211; Immutable"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 304. Range Sum Query 2D - Immutable - \u5237\u9898\u627e\u5de5\u4f5c EP63\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/MSNSqU3BnXk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/range-sum-query-2d-immutable\/description\/\">https:\/\/leetcode.com\/problems\/range-sum-query-2d-immutable\/description\/<\/a><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<div class=\"question-description\">\n<p>Given a 2D matrix\u00a0<i>matrix<\/i>, find the sum of the elements inside the rectangle defined by its upper left corner (<i>row<\/i>1,\u00a0<i>col<\/i>1) and lower right corner (<i>row<\/i>2,\u00a0<i>col<\/i>2).<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/leetcode.com\/static\/images\/courses\/range_sum_query_2d.png\" alt=\"Range Sum Query 2D\" border=\"0\" \/><br \/>\n<small>The above rectangle (with the red border) is defined by (row1, col1) =\u00a0<b>(2, 1)<\/b>\u00a0and (row2, col2) =\u00a0<b>(4, 3)<\/b>, which contains sum =\u00a0<b>8<\/b>.<\/small><\/p>\n<p><b>Example:<\/b><\/p>\n<pre class=\"\">Given matrix = [\r\n  [3, 0, 1, 4, 2],\r\n  [5, 6, 3, 2, 1],\r\n  [1, 2, 0, 1, 5],\r\n  [4, 1, 0, 1, 7],\r\n  [1, 0, 3, 0, 5]\r\n]\r\n\r\nsumRegion(2, 1, 4, 3) : 8\r\nsumRegion(1, 1, 2, 2) : 11\r\nsumRegion(1, 2, 2, 4) : 12\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>You may assume that the matrix does not change.<\/li>\n<li>There are many calls to\u00a0<i>sumRegion<\/i>\u00a0function.<\/li>\n<li>You may assume that\u00a0<i>row<\/i>1 \u2264\u00a0<i>row<\/i>2 and\u00a0<i>col<\/i>1 \u2264\u00a0<i>col<\/i>2.<\/li>\n<\/ol>\n<\/div>\n<div id=\"interviewed-div\"><strong>Idea:<\/strong><\/div>\n<div><\/div>\n<div>Dynamic programming<\/div>\n<div><\/div>\n<div>Time complexity:<\/div>\n<div>O(n^2)<\/div>\n<div>sumRegion: O(1)<\/div>\n<div><\/div>\n<div><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-353\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-352\" style=\"font-size: 1rem;\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/304-ep63-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/div>\n<div><\/div>\n<div><strong>Solution:<\/strong><\/div>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<div>\n<pre class=\"lang:c++ decode:true  \">\/\/ Author: Huahua\r\n\/\/ Time complexity: \r\n\/\/ constructor: O(n^2)\r\n\/\/ sumRegion: O(1)\r\n\/\/ Running time: 22 ms 9\/2017\r\nclass NumMatrix {\r\npublic:\r\n    NumMatrix(const vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {\r\n        sums_.clear();\r\n        \r\n        if (matrix.empty()) return;\r\n        \r\n        int m = matrix.size();        \r\n        int n = matrix[0].size();\r\n        \r\n        \/\/ sums_[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])\r\n        sums_ = vector&lt;vector&lt;int&gt;&gt;(m + 1, vector&lt;int&gt;(n + 1, 0));\r\n        for (int i = 1; i &lt;= m; ++i)\r\n            for (int j = 1; j &lt;= n; ++j)\r\n                sums_[i][j] = matrix[i - 1][j - 1]\r\n                            + sums_[i - 1][j]\r\n                            + sums_[i][j - 1]\r\n                            - sums_[i - 1][j - 1];\r\n    }\r\n    \r\n    int sumRegion(int row1, int col1, int row2, int col2) {        \r\n        return sums_[row2 + 1][col2 + 1]\r\n             - sums_[row2 + 1][col1]\r\n             - sums_[row1][col2 + 1]\r\n             + sums_[row1][col1];\r\n    }\r\nprivate:\r\n    vector&lt;vector&lt;int&gt;&gt; sums_;\r\n};\r\n\r\n\/**\r\n * Your NumMatrix object will be instantiated and called as such:\r\n * NumMatrix obj = new NumMatrix(matrix);\r\n * int param_1 = obj.sumRegion(row1,col1,row2,col2);\r\n *\/<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; https:\/\/leetcode.com\/problems\/range-sum-query-2d-immutable\/description\/ Problem: Given a 2D matrix\u00a0matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1,\u00a0col1) and lower&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,98,62],"class_list":["post-348","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-range-query","tag-sum","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/348","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=348"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/348\/revisions"}],"predecessor-version":[{"id":3053,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/348\/revisions\/3053"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=348"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}