{"id":1182,"date":"2023-12-25T17:09:49","date_gmt":"2023-12-25T09:09:49","guid":{"rendered":"http:\/\/www.forillusion.com\/?p=1182"},"modified":"2025-02-14T11:39:10","modified_gmt":"2025-02-14T03:39:10","slug":"prefixsum-and-difference","status":"publish","type":"post","link":"https:\/\/www.forillusion.com\/index.php\/prefixsum-and-difference\/","title":{"rendered":"\u524d\u7f00\u548c\u4e0e\u5dee\u5206"},"content":{"rendered":"\n<p><div class=\"has-toc have-toc\"><\/div><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u6a21\u7248<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">\/\/\u7528a\u8868\u793a\u539f\u6570\u7ec4originalArray\uff0c\u7528p\u8868\u793a\u524d\u7f00\u548cprefixSum,\u7528d\u8868\u793a\u5dee\u5206difference\n\/\/\u4e00\u7ef4\u524d\u7f00\na&#91;0]=p&#91;0]=0;\np&#91;i]=a&#91;i]+p&#91;i-1];   \/\/\u751f\u6210\u524d\u7f00\u548c\na&#91;i]=p&#91;i]-p&#91;i-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nsum=p&#91;r]-p&#91;l-1];   \/\/\u6c42\u533a\u95f4l-r\u7684\u548c\n\/\/\u4e00\u7ef4\u5dee\u5206\na&#91;0]=d&#91;0]=0;\nd&#91;i]=a&#91;i]-a&#91;i-1];   \/\/\u751f\u6210\u5dee\u5206\u6570\u7ec4\na&#91;i]=a&#91;i-1]+d&#91;i];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nd&#91;l]+=c;   \/\/\u5c06\u533a\u95f4l-r\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\u52a0c\nd&#91;r+1]-=c;\n\n\/\/\u4e8c\u7ef4\u524d\u7f00\u548c\np&#91;i]&#91;j]=a&#91;i]&#91;j]+p&#91;i-1]&#91;j]+p&#91;i]&#91;j-1]-p&#91;i-1]&#91;j-1];   \/\/\u751f\u6210\u524d\u7f00\u548c\na&#91;i]&#91;j]=p&#91;i]&#91;j]-p&#91;i-1]&#91;j]-p&#91;i]&#91;j-1]+p&#91;i-1]&#91;j-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nsum=p&#91;x2]&#91;y2]-p&#91;x1-1]&#91;y2]-p&#91;x2]&#91;y1-1]+p&#91;x1-1]&#91;y1-1];   \/\/\u6c42\u533a\u95f4(x1,y1)-(x2,y2)\u7684\u548c\n\/\/\u4e8c\u7ef4\u5dee\u5206\nd&#91;i]&#91;j]=a&#91;i]&#91;j]-a&#91;i-1]&#91;j]-a&#91;i]&#91;j-1]+a&#91;i-1]&#91;j-1];   \/\/\u751f\u6210\u5dee\u5206\u6570\u7ec4\na&#91;i]&#91;j]=d&#91;i]&#91;j]+a&#91;i-1]&#91;j]+a&#91;i]&#91;j-1]-a&#91;i-1]&#91;j-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nd&#91;x1]&#91;y1]+=c;   \/\/\u5c06\u533a\u95f4(x1,y1)-(x2,y2)\u7684\u52a0c\nd&#91;x2+1]&#91;y1]-=c;\nd&#91;x1]&#91;y2+1]-=c;\nd&#91;x2+1]&#91;y2+1]+=c;   \n\n\/\/\u4e09\u7ef4\u524d\u7f00\u548c\np&#91;x]&#91;y]&#91;z]=a&#91;x]&#91;y]&#91;z]+p&#91;x-1]&#91;y]&#91;z]+p&#91;x]&#91;y-1]&#91;z]+p&#91;x]&#91;y]&#91;z-1]-p&#91;x-1]&#91;y-1]&#91;z]-p&#91;x-1]&#91;y]&#91;z-1]-p&#91;x]&#91;y-1]&#91;z-1]+p&#91;x-1]&#91;y-1]&#91;z-1];   \/\/\u751f\u6210\u524d\u7f00\u548c\na&#91;x]&#91;y]&#91;z]=p&#91;x]&#91;y]&#91;z]-p&#91;x-1]&#91;y]&#91;z]-p&#91;x]&#91;y-1]&#91;z]-p&#91;x]&#91;y]&#91;z-1]+p&#91;x-1]&#91;y-1]&#91;z]+p&#91;x-1]&#91;y]&#91;z-1]+p&#91;x]&#91;y-1]&#91;z-1]-p&#91;x-1]&#91;y-1]&#91;z-1];\n   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nsum=p&#91;x2]&#91;y2]&#91;z2]-p&#91;x1-1]&#91;y2]&#91;z2]-p&#91;x2]&#91;y1-1]&#91;z2]-p&#91;x2]&#91;y2]&#91;z1-1]+p&#91;x1-1]&#91;y1-1]&#91;z2]+p&#91;x1-1]&#91;y2]&#91;z1-1]+p&#91;x2]&#91;y1-1]&#91;z1-1]-p&#91;x1-1]&#91;y1-1]&#91;z1-1];   \/\/\u6c42\u533a\u95f4(x1,y1,z1)-(x2,y2,z2)\u7684\u548c\n\/\/\u4e09\u7ef4\u5dee\u5206\nd&#91;x]&#91;y]&#91;z]=a&#91;x]&#91;y]&#91;z]-a&#91;x-1]&#91;y]&#91;z]-a&#91;x]&#91;y-1]&#91;z]-a&#91;x]&#91;y]&#91;z-1]+a&#91;x-1]&#91;y-1]&#91;z]+a&#91;x-1]&#91;y]&#91;z-1]+a&#91;x]&#91;y-1]&#91;z-1]-a&#91;x-1]&#91;y-1]&#91;z-1];   \/\/\u751f\u6210\u5dee\u5206\u6570\u7ec4\na&#91;x]&#91;y]&#91;z]=d&#91;x]&#91;y]&#91;z]+a&#91;x-1]&#91;y]&#91;z]+a&#91;x]&#91;y-1]&#91;z]+a&#91;x]&#91;y]&#91;z-1]-a&#91;x-1]&#91;y-1]&#91;z]-a&#91;x-1]&#91;y]&#91;z-1]-a&#91;x]&#91;y-1]&#91;z-1]+a&#91;x-1]&#91;y-1]&#91;z-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nd&#91;x1]&#91;y1]&#91;z1]+=c;   \/\/\u5c06\u533a\u95f4(x1,y1,z1)-(x2,y2,z2)\u4e2d\u7684\u6bcf\u4e00\u4e2a\u5143\u7d20\u52a0c\nd&#91;x2+1]&#91;y1]&#91;z1]-=c;\nd&#91;x1]&#91;y1]&#91;z2+1]-=c;\nd&#91;x2+1]&#91;y1]&#91;z2+1]+=c;\nd&#91;x1]&#91;y2+1]&#91;z1]-=c;\nd&#91;x2+1]&#91;y2+1]&#91;z1]+=c;\nd&#91;x1]&#91;y2+1]&#91;z2+1]+=c;\nd&#91;x2+1]&#91;y2+1]&#91;z2+1]-=c;<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e00\u7ef4<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u524d\u7f00\u548c<\/h3>\n\n\n\n<p>\u524d\u7f00\u548c\u662f\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u5143\u7d20\u90fd\u662f\u5143\u7d20\u7684\u539f\u6570\u636e\u52a0\u4e0a\u524d\u9762\u7684\u6240\u6709\u5143\u7d20\u7684\u548c\u3002\u53ef\u4ee5\u7528\u6765\u6c42\u533a\u95f4\u548c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>\u539f\u6570\u7ec4\uff1a<\/td><td>1<\/td><td>2<\/td><td>3<\/td><td>4<\/td><td>5<\/td><td>6<\/td><\/tr><tr><td>\u524d\u7f00\u548c\uff1a<\/td><td>1<\/td><td>3<\/td><td>6<\/td><td>10<\/td><td>15<\/td><td>21<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>\u524d\u7f00\u548c\u6570\u7ec4\u8bb0\u5f55\u7684\u662f\u5f53\u524d\u5143\u7d20\u4ee5\u53ca\u524d\u9762\u6240\u6709\u7684\u5143\u7d20\u7684\u4fe1\u606f\u3002<br>\u4e00\u822c\u5728\u751f\u6210\u524d\u7f00\u548c\u65f6\u4e0b\u6807\u90fd\u4ece1\u5f00\u59cb\uff0c\u5e76\u5b9a\u4e49originalArray[0]=prefixSum[0]=0;<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">a&#91;0]=p&#91;0]=0;\np&#91;i]=a&#91;i]+p&#91;i-1];   \/\/\u751f\u6210\u524d\u7f00\u548c\na&#91;i]=p&#91;i]-p&#91;i-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nsum=p&#91;r]-p&#91;l-1];   \/\/\u6c42\u533a\u95f4l-r\u7684\u548c<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u5dee\u5206<\/h3>\n\n\n\n<p>\u5dee\u5206\u6307\u7684\u662f\u53d8\u5316\u91cf\uff0c\u5dee\u5206\u6570\u7ec4\u8bb0\u5f55\u7684\u662f\u5f53\u524d\u5143\u7d20\u548c\u524d\u9762\u4e00\u4e2a\u5143\u7d20\u7684\u5dee\u503c\u3002\u53ef\u4ee5\u7528\u6765\u5feb\u901f\u7684\u5bf9\u4e00\u4e2a\u533a\u95f4\u7684\u5143\u7d20\u7edf\u4e00\u52a0\u3001\u51cf\u4e00\u4e2a\u6570\uff0c\u800c\u4e0d\u5fc5\u4f9d\u6b21\u4fee\u6539\u533a\u95f4\u7684\u6bcf\u4e00\u4e2a\u6570\u3002<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>\u539f\u6570\u7ec4\uff1a<\/td><td>1<\/td><td>3<\/td><td>5<\/td><td>2<\/td><td>4<\/td><td>6<\/td><\/tr><tr><td>\u5dee\u5206\u6570\u7ec4\uff1a<\/td><td>1<\/td><td>2<\/td><td>2<\/td><td>-3<\/td><td>2<\/td><td>2<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>\u5dee\u5206\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u5143\u7d20\u53ea\u8bb0\u5f55\u4e86\u5f53\u524d\u5143\u7d20\u548c\u524d\u9762\u5143\u7d20\u7684\u5173\u7cfb\uff0c\u5e76\u4e0d\u643a\u5e26\u524d\u9762\u6240\u6709\u5143\u7d20\u7684\u4fe1\u606f\u3002\u540c\u6837\u4e0b\u6807\u9ed8\u8ba4\u4ece1\u5f00\u59cb\uff0c\u5e76\u5b9a\u4e49originalArray[0]=difference[0]=0;<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">a&#91;0]=d&#91;0]=0;\nd&#91;i]=a&#91;i]-a&#91;i-1];   \/\/\u751f\u6210\u5dee\u5206\u6570\u7ec4\na&#91;i]=a&#91;i-1]+d&#91;i];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nd&#91;l]+=c;   \/\/\u5c06\u533a\u95f4l-r\u4e2d\u7684\u6bcf\u4e2a\u5143\u7d20\u52a0c\nd&#91;r+1]-=c;<\/code><\/pre>\n\n\n\n<p>\u89c2\u5bdf\u516c\u5f0f\u53d1\u73b0\uff0c\u8fd8\u539f\u539f\u6570\u7ec4\u7684\u8fc7\u7a0b\u5c31\u662f\u5bf9\u5dee\u5206\u6570\u7ec4\u6c42\u524d\u7f00\u548c\u3002<br>\u5728\u4fee\u6539\u533a\u95f4\u7684\u65f6\u5019\uff0c\u5c06difference[l]\u52a0a\u5373\u6539\u53d8\u4e86l\u5143\u7d20\u4e0el-1\u5143\u7d20\u7684\u5dee\uff0c\u4f46\u662f\u540e\u9762\u5143\u7d20\u7684\u5dee\u5206\u4e0d\u53d8\uff0c\u6240\u4ee5l\u540e\u9762\u7684\u6570\u90fd\u4f1a\u88ab\u52a0a\uff0cdifference[r+1]\u51cfa\uff0c\u5373\u6539\u53d8\u4e86r+1\u5143\u7d20\u4e0er\u5143\u7d20\u7684\u5dee\uff0c\u628a\u539f\u672c\u589e\u52a0\u6570\u518d\u51cf\u53bb\uff0c\u4f7f\u5f97r\u540e\u9762\u7684\u6570\u5148\u52a0a\u518d\u51cfa\uff0c\u5373\u4e0d\u53d8\u3002\u8fd9\u6837\u5c31\u505a\u5230\u4e86\u4fee\u6539\u533a\u95f4l-r\u7684\u6570\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e8c\u7ef4<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u524d\u7f00\u548c<\/h3>\n\n\n\n<p>\u4e0e\u4e00\u7ef4\u524d\u7f00\u548c\u4e00\u6837\uff0c\u4e8c\u7ef4\u524d\u7f00\u548c\u662f\u5f53\u524d\u5143\u7d20\u548c\u524d\u9762\u6240\u6709\u5143\u7d20\u7684\u548c\u3002\u8fd9\u91cc\u7684\u524d\u9762\u6240\u6709\u5143\u7d20\u6307\u7684\u662f\u4ece(0,0)\u5230(i,j)\u8fd9\u4e24\u70b9\u6240\u5f62\u6210\u7684\u77e9\u5f62\u533a\u57df\u3002<\/p>\n\n\n\n<p>\u5728\u8ba1\u7b97\u524d\u7f00\u548c\u65f6\uff0c\u4e0d\u4f1a\u5c06\u5f53\u524d\u5143\u7d20\u4f9d\u6b21\u4e0e\u524d\u9762\u6bcf\u4e00\u4e2a\u5143\u7d20\u76f8\u52a0\uff0c\u800c\u662f\u5229\u7528\u524d\u9762\u8ba1\u7b97\u597d\u7684\u524d\u7f00\u548c\uff0c\u518d\u52a0\u4e0a\u5f53\u524d\u5143\u7d20\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-20.png\" src=\"https:\/\/cdn.forillusion.com\/moezx\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  alt=\"\" class=\"wp-image-1184\" width=\"284\" height=\"301\" srcset=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-20.png 422w, https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-20-283x300.png 283w\" sizes=\"auto, (max-width: 284px) 100vw, 284px\" \/><\/figure >\n<noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-20.png\" alt=\"\" class=\"wp-image-1184\" width=\"284\" height=\"301\" srcset=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-20.png 422w, https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-20-283x300.png 283w\" sizes=\"auto, (max-width: 284px) 100vw, 284px\" \/><\/figure><\/noscript>\n\n\n\n<p>\u5982\u56fe\uff0c\u7528\u6bcf\u4e00\u4e2a\u683c\u5b50\u8868\u793a\u4e00\u4e2a\u5143\u7d20\uff0c\u4e0b\u6807\u4ece(1,1)\u5f00\u59cb\u3002\u4ee4\u884c\u4e3ai\uff0c\u5217\u4e3aj\u3002\u5982\u679c\u60f3\u8981\u6c42(6,F)\u4f4d\u7f6e\u7684\u524d\u7f00\u548c\uff0c\u5982\u679c\u5c06(6,F)\u4e0e(6,E)\u7684\u524d\u7f00\u548c\u76f8\u52a0\uff08\u7070\u8272\uff0c\u7eff\u8272\u4e0e\u7d2b\u8272\u533a\u57df\uff09\uff0c\u5219\u4f1a\u6f0f\u6389\u7b2cF\u5217\u7684\u6570\u636e(\u7ea2\u8272\u533a\u57df)\u3002\u540c\u7406\uff0c(6,F)\u4e0e(5,F)\u7684\u524d\u7f00\u548c\u76f8\u52a0\uff08\u7070\u8272\uff0c\u7ea2\u8272\u4e0e\u7d2b\u8272\u533a\u57df\uff09\uff0c\u5219\u4f1a\u6f0f\u6389\u7b2c6\u884c\u7684\u6570\u636e\uff08\u7eff\u8272\u533a\u57df\uff09\u3002\u6240\u4ee5\u540c\u65f6\u5c06(6,F)\u4e0e(6,E)(5,F)\u7684\u524d\u7f00\u548c\u76f8\u52a0\uff0c\u5c31\u4e0d\u4f1a\u6709\u9057\u6f0f\u7684\u5143\u7d20\uff0c\u4f46\u662f\u8fd9\u65f6(5,E)\u7684\u524d\u7f00\u548c\uff08\u7d2b\u8272\u533a\u57df\uff09\u4f1a\u88ab\u91cd\u590d\u8ba1\u7b97\uff0c\u6240\u4ee5\u9700\u8981\u518d\u51cf\u4e00\u6b21(5,E)\u7684\u524d\u7f00\u548c\u3002<\/p>\n\n\n\n<p>\u540c\u6837\uff0c\u5728\u6839\u636e\u524d\u7f00\u548c\u8fd8\u539f\u539f\u6570\u7ec4\u7684\u65f6\u5019\uff0c\u5c06(6,F)\u7684\u524d\u7f00\u548c\u51cf\u53bb(6,E)(5,F)\u7684\u524d\u7f00\u548c\u65f6\uff0c(5,E)\u7684\u524d\u7f00\u548c\uff08\u7d2b\u8272\u533a\u57df\uff09\u4f1a\u88ab\u91cd\u590d\u51cf\u53bb\uff0c\u6240\u4ee5\u8981\u518d\u52a0\u4e00\u6b21(5,E)\u7684\u524d\u7f00\u548c\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">p&#91;i]&#91;j]=a&#91;i]&#91;j]+p&#91;i-1]&#91;j]+p&#91;i]&#91;j-1]-p&#91;i-1]&#91;j-1];   \/\/\u751f\u6210\u524d\u7f00\u548c\na&#91;i]&#91;j]=p&#91;i]&#91;j]-p&#91;i-1]&#91;j]-p&#91;i]&#91;j-1]+p&#91;i-1]&#91;j-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-21.png\" src=\"https:\/\/cdn.forillusion.com\/moezx\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  alt=\"\" class=\"wp-image-1185\" width=\"294\" height=\"319\" srcset=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-21.png 412w, https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-21-277x300.png 277w\" sizes=\"auto, (max-width: 294px) 100vw, 294px\" \/><\/figure >\n<noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-21.png\" alt=\"\" class=\"wp-image-1185\" width=\"294\" height=\"319\" srcset=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-21.png 412w, https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-21-277x300.png 277w\" sizes=\"auto, (max-width: 294px) 100vw, 294px\" \/><\/figure><\/noscript>\n\n\n\n<p>\u5982\u56fe\uff0c\u5728\u5229\u7528\u524d\u7f00\u548c\u6c42(5,D)\u5230(6,F)\u8fd9\u4e2a\u533a\u95f4\u7684\u548c\u65f6\uff0c\u53ef\u4ee5\u7528(6-F)\u7684\u524d\u7f00\u548c\u51cf\u53bb(6,C)\uff08\u7eff\u8272\u4e0e\u7d2b\u8272\u533a\u57df\uff09\u4e0e(4,F)\uff08\u7ea2\u8272\u4e0e\u7d2b\u8272\u533a\u57df\uff09\u7684\u524d\u7f00\u548c\uff0c\u4f46\u540c\u65f6(4,C)\u7684\u524d\u7f00\u548c\uff08\u7d2b\u8272\u533a\u57df\uff09\u88ab\u51cf\u53bb\u7684\u4e86\u4e24\u6b21\uff0c\u6240\u4ee5\u8981\u518d\u52a0\u4e00\u6b21(4,C)\u7684\u524d\u7f00\u548c<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">sum=p&#91;x2]&#91;y2]-p&#91;x1-1]&#91;y2]-p&#91;x2]&#91;y1-1]+p&#91;x1-1]&#91;y1-1];   \/\/\u6c42\u533a\u95f4(x1,y1)-(x2,y2)\u7684\u548c<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u5dee\u5206<\/h3>\n\n\n\n<p>\u5728\u4e00\u7ef4\u5dee\u5206\u4e2d\uff0c\u8fd8\u539f\u539f\u6570\u7ec4\u7684\u8fc7\u7a0b\u5c31\u662f\u5bf9\u5dee\u5206\u6570\u7ec4\u6c42\u524d\u7f00\u548c\u3002<br>\u540c\u6837\u53ef\u4ee5\u5f97\u51fa\uff0c\u4e8c\u7ef4\u5dee\u5206\u4e2d\uff0c\u8fd8\u539f\u539f\u6570\u7ec4\u7684\u8fc7\u7a0b\u5c31\u662f\u5bf9\u4e8c\u7ef4\u5dee\u5206\u6570\u7ec4\u6c42\u524d\u7f00\u548c\uff0c\u5373\u539f\u6570\u7ec4=\u5dee\u5206\u6570\u7ec4\u7684\u524d\u7f00\u548c\uff1aa[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];<br>\u53d8\u5f62\u516c\u5f0f\u53ef\u5f97\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">d&#91;i]&#91;j]=a&#91;i]&#91;j]-a&#91;i-1]&#91;j]-a&#91;i]&#91;j-1]+a&#91;i-1]&#91;j-1];   \/\/\u751f\u6210\u5dee\u5206\u6570\u7ec4\na&#91;i]&#91;j]=d&#91;i]&#91;j]+a&#91;i-1]&#91;j]+a&#91;i]&#91;j-1]-a&#91;i-1]&#91;j-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-23.png\" src=\"https:\/\/cdn.forillusion.com\/moezx\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  alt=\"\" class=\"wp-image-1188\" width=\"286\" height=\"315\" srcset=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-23.png 409w, https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-23-273x300.png 273w\" sizes=\"auto, (max-width: 286px) 100vw, 286px\" \/><\/figure >\n<noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-23.png\" alt=\"\" class=\"wp-image-1188\" width=\"286\" height=\"315\" srcset=\"https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-23.png 409w, https:\/\/cos.forillusion.top\/wp-content\/uploads\/2023\/12\/image-23-273x300.png 273w\" sizes=\"auto, (max-width: 286px) 100vw, 286px\" \/><\/figure><\/noscript>\n\n\n\n<p>\u5982\u56fe\uff0c\u5728\u4fee\u6539\u4e8c\u7ef4\u5dee\u5206\u6570\u7ec4\u4e2d\u7684\u4e00\u4e2a\u5143\u7d20\u65f6\uff0c\u5982(4,C)\uff0c\u4f1a\u5bfc\u81f4(4,C)\u53ca\u540e\u9762\u7684\u6240\u6709\u5143\u7d20\u90fd\u88ab\u6539\u53d8\uff08\u7070\u8272\u3001\u7ea2\u8272\u3001\u7eff\u8272\u3001\u7d2b\u8272\u533a\u57df\uff09\u3002\u6240\u4ee5\u60f3\u8981\u4ec5\u4fee\u6539\u7070\u8272\u533a\u57df\u7684\u6570\u636e\uff08\u52a0a\uff09\uff0c\u53ef\u4ee5\u5c06(4,C)\u52a0a\uff0c\u7136\u540e\u5c06(4,F)\u7684\u5dee\u5206\uff08\u7ea2\u8272\u548c\u7d2b\u8272\u533a\u57df\uff09\u548c(6,C)\u7684\u5dee\u5206\uff08\u7eff\u8272\u548c\u7d2b\u8272\u7684\u533a\u57df\uff09\u51cfa\uff0c\u6765\u62b5\u6d88(4,C)\u52a0a\u9020\u6210\u7684\u6570\u503c\u6539\u53d8\uff0c\u4f46\u662f\u4f1a\u5bfc\u81f4(6,F)\u540e\u9762\u533a\u57df\u7684\u6570\u503c\uff08\u7d2b\u8272\u533a\u57df\uff09\u88ab\u51cf\u4e86\u4e24\u6b21a\uff0c\u6240\u4ee5\u9700\u8981\u5c06(6,F)\u7684\u5dee\u5206\u518d\u52a0\u4e00\u6b21a\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">d&#91;x1]&#91;y1]+=c;   \/\/\u5c06\u533a\u95f4(x1,y1)-(x2,y2)\u7684\u52a0c\nd&#91;x2+1]&#91;y1]-=c;\nd&#91;x1]&#91;y2+1]-=c;\nd&#91;x2+1]&#91;y2+1]+=c;   <\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u4e09\u7ef4<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u524d\u7f00\u548c<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">p&#91;x]&#91;y]&#91;z]=a&#91;x]&#91;y]&#91;z]+p&#91;x-1]&#91;y]&#91;z]+p&#91;x]&#91;y-1]&#91;z]+p&#91;x]&#91;y]&#91;z-1]-p&#91;x-1]&#91;y-1]&#91;z]-p&#91;x-1]&#91;y]&#91;z-1]-p&#91;x]&#91;y-1]&#91;z-1]+p&#91;x-1]&#91;y-1]&#91;z-1];   \/\/\u751f\u6210\u524d\u7f00\u548c\na&#91;x]&#91;y]&#91;z]=p&#91;x]&#91;y]&#91;z]-p&#91;x-1]&#91;y]&#91;z]-p&#91;x]&#91;y-1]&#91;z]-p&#91;x]&#91;y]&#91;z-1]+p&#91;x-1]&#91;y-1]&#91;z]+p&#91;x-1]&#91;y]&#91;z-1]+p&#91;x]&#91;y-1]&#91;z-1]-p&#91;x-1]&#91;y-1]&#91;z-1];\n   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nsum=p&#91;x2]&#91;y2]&#91;z2]-p&#91;x1-1]&#91;y2]&#91;z2]-p&#91;x2]&#91;y1-1]&#91;z2]-p&#91;x2]&#91;y2]&#91;z1-1]+p&#91;x1-1]&#91;y1-1]&#91;z2]+p&#91;x1-1]&#91;y2]&#91;z1-1]+p&#91;x2]&#91;y1-1]&#91;z1-1]-p&#91;x1-1]&#91;y1-1]&#91;z1-1];   \/\/\u6c42\u533a\u95f4(x1,y1,z1)-(x2,y2,z2)\u7684\u548c<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u5dee\u5206<\/h3>\n\n\n\n<p>\u548c\u4e8c\u7ef4\u5dee\u5206\u4e00\u6837\uff0c\u5229\u7528\u539f\u6570\u7ec4=\u5dee\u5206\u6570\u7ec4\u7684\u524d\u7f00\u548c\u6c42\u51fa\u4e09\u7ef4\u5dee\u5206\u7684\u516c\u5f0f\u3002<br>a[x][y][z]=d[x][y][z]+a[x-1][y][z]+a[x][y-1][z]+a[x][y][z-1]-a[x-1][y-1][z]-a[x-1][y][z-1]-a[x][y-1][z-1]+a[x-1][y-1][z-1];<br>\u53d8\u5f62\u540e\u5f97\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"cpp\">d&#91;x]&#91;y]&#91;z]=a&#91;x]&#91;y]&#91;z]-a&#91;x-1]&#91;y]&#91;z]-a&#91;x]&#91;y-1]&#91;z]-a&#91;x]&#91;y]&#91;z-1]+a&#91;x-1]&#91;y-1]&#91;z]+a&#91;x-1]&#91;y]&#91;z-1]+a&#91;x]&#91;y-1]&#91;z-1]-a&#91;x-1]&#91;y-1]&#91;z-1];   \/\/\u751f\u6210\u5dee\u5206\u6570\u7ec4\na&#91;x]&#91;y]&#91;z]=d&#91;x]&#91;y]&#91;z]+a&#91;x-1]&#91;y]&#91;z]+a&#91;x]&#91;y-1]&#91;z]+a&#91;x]&#91;y]&#91;z-1]-a&#91;x-1]&#91;y-1]&#91;z]-a&#91;x-1]&#91;y]&#91;z-1]-a&#91;x]&#91;y-1]&#91;z-1]+a&#91;x-1]&#91;y-1]&#91;z-1];   \/\/\u8fd8\u539f\u539f\u6570\u7ec4\nd&#91;x1]&#91;y1]&#91;z1]+=c;   \/\/\u5c06\u533a\u95f4(x1,y1,z1)-(x2,y2,z2)\u4e2d\u7684\u6bcf\u4e00\u4e2a\u5143\u7d20\u52a0c\nd&#91;x2+1]&#91;y1]&#91;z1]-=c;\nd&#91;x1]&#91;y1]&#91;z2+1]-=c;\nd&#91;x2+1]&#91;y1]&#91;z2+1]+=c;\nd&#91;x1]&#91;y2+1]&#91;z1]-=c;\nd&#91;x2+1]&#91;y2+1]&#91;z1]+=c;\nd&#91;x1]&#91;y2+1]&#91;z2+1]+=c;\nd&#91;x2+1]&#91;y2+1]&#91;z2+1]-=c;<\/code><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6a21\u7248 \u4e00\u7ef4 \u524d\u7f00\u548c \u524d\u7f00\u548c\u662f\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u5143\u7d20\u90fd\u662f\u5143\u7d20\u7684\u539f\u6570\u636e\u52a0\u4e0a\u524d\u9762\u7684\u6240\u6709\u5143\u7d20\u7684\u548c\u3002\u53ef\u4ee5\u7528\u6765\u6c42\u533a\u95f4\u548c\u3002 \u539f\u6570\u7ec4\uff1a 1 2 3 4  &#8230;<\/p>","protected":false},"author":1,"featured_media":1221,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,35],"tags":[43,12,34,22],"class_list":["post-1182","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-3","category-35","tag-43","tag-12","tag-34","tag-22"],"_links":{"self":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/comments?post=1182"}],"version-history":[{"count":1,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1182\/revisions"}],"predecessor-version":[{"id":1745,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/posts\/1182\/revisions\/1745"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/media\/1221"}],"wp:attachment":[{"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/media?parent=1182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/categories?post=1182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.forillusion.com\/index.php\/wp-json\/wp\/v2\/tags?post=1182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}