{"id":613,"date":"2023-03-20T19:52:46","date_gmt":"2023-03-20T11:52:46","guid":{"rendered":"https:\/\/lolife.top\/?p=613"},"modified":"2023-03-21T19:13:39","modified_gmt":"2023-03-21T11:13:39","slug":"%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"https:\/\/lolife.top\/?p=613","title":{"rendered":"\u6811\u72b6\u6570\u7ec4"},"content":{"rendered":"\n<p>\u6811\u72b6\u6570\u7ec4\u4e3b\u8981\u662f\u7528\u6765\u89e3\u51b3\u52a8\u6001\u524d\u7f00\u548c\u95ee\u9898\uff1b\u4e00\u822c\u6765\u8bf4\uff0c\u95ee\u9898\u662f\u8fd9\u4e48\u95ee\u7684\uff1a<\/p>\n\n\n\n<p>\u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u6709m\u6b21\u64cd\u7eb5\uff08\u9009\u62e9\u6570\u7ec4\u4e2d\u7684\u4e00\u4e2a\u5143\u7d20\u5e76\u8ba9\u5176\u52a0v\uff09\u4ee5\u53caq\u6b21\u8be2\u95ee\uff08\u67e5\u8be2a[1]+a[2]+a[3]+&#8230;+a[x]\u7684\u503c\uff09<\/p>\n\n\n\n<p>\u5982\u679c\u7528\u66b4\u529b\u7684\u65b9\u6cd5\uff0c\u6bcf\u6b21\u64cd\u4f5c\u7684\u65f6\u95f4\u590d\u6742\u7684\u4e3aO(1)\uff0c\u800c\u6bcf\u6b21\u67e5\u8be2\u7684\u65f6\u95f4\u590d\u6742\u5ea6O(n)\uff0cn\u4e3a\u6570\u7ec4\u7684\u957f\u5ea6\uff1b<\/p>\n\n\n\n<p>\u6240\u4ee5\u603b\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(qn)\uff1b\u663e\u7136\u4e0d\u884c\uff0c\u6240\u4ee5\u5c31\u7528\u5230\u4e86\u6811\u72b6\u6570\u7ec4\u3002<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>\u6811\u72b6\u6570\u7ec4\u5927\u6982\u957f\u8fd9\u6837\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><div class='fancybox-wrapper lazyload-container-unload' data-fancybox='post-images' href='http:\/\/image.lolife.top\/2023\/03\/image-2-1024x456.png'><img class=\"lazyload lazyload-style-1\" src=\"data:image\/svg+xml;base64,PCEtLUFyZ29uTG9hZGluZy0tPgo8c3ZnIHdpZHRoPSIxIiBoZWlnaHQ9IjEiIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgc3Ryb2tlPSIjZmZmZmZmMDAiPjxnPjwvZz4KPC9zdmc+\"  loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"456\" data-original=\"http:\/\/image.lolife.top\/2023\/03\/image-2-1024x456.png\" src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsQAAA7EAZUrDhsAAAANSURBVBhXYzh8+PB\/AAffA0nNPuCLAAAAAElFTkSuQmCC\" alt=\"\" class=\"wp-image-616\"  sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/div><\/figure>\n\n\n\n<p>\u6211\u4eec\u77e5\u9053\uff0c\u524d\u7f00\u548c\u6570\u7ec4\u7684\u6bcf\u4e00\u4f4d\u8bb0\u5f55\u7684\u662f\u4ece\u5f00\u59cb\u5230\u5f53\u524d\u4f4d\u7f6e\u7684\u6240\u6709\u5143\u7d20\u7684\u548c\uff0c\u800c\u6811\u72b6\u6570\u7ec4\u4e5f\u662f\u7c7b\u4f3c\u7684\uff0c<\/p>\n\n\n\n<p>\u5bf9\u4e8e\u4e0a\u56fe\uff0c\u8282\u70b94\u8bb0\u5f55\u7684\u662fa[1]\u5230a[4]\u7684\u548c,a[3]\u8bb0\u5f55\u7684\u662fa[3]\u5230a[3]\u7684\u548c\uff0c\u4e5f\u5c31\u662fa[3];\u6811\u72b6\u6570\u7ec4\u662f\u5c06\u6570\u7ec4\u5206\u6210\u4e86\u82e5\u5e72\u6bb5\uff0c\u6bcf\u6b21\u4fee\u6539\u53ea\u9700\u8981\u6539\u8986\u76d6\u5230\u5f53\u524d\u8282\u70b9\u7684\u533a\u95f4\uff0c\u4f8b\u5982\u8981\u4fee\u6539\u8282\u70b96\u7684\u503c\uff0c\u6211\u4eec\u53ea\u9700\u8981\u66f4\u65b0a[6]\u3001a[8]\u3001a[16]\uff1b\u5982\u679c\u8981\u67e5\u8be2\u67d0\u4e2a\u4f4d\u7f6e\u7684\u524d\u7f00\u548c\uff0c\u4f8b\u5982\u8282\u70b911\uff0c\u6211\u4eec\u53ea\u9700\u8981\u67e5\u8be2a[8]\u3001a[10]\u3001a[11]\u7684\u503c\u7136\u540e\u76f8\u52a0\u5373\u53ef\u3002<\/p>\n\n\n\n<p>\u539f\u7406\u5f88\u7b80\u5355\uff0c\u90a3\u73b0\u5728\u95ee\u9898\u6765\u4e86\uff0c\u6211\u4eec\u600e\u4e48\u77e5\u9053\u8981\u4fee\u6539\u6216\u8005\u67e5\u8be2\u54ea\u4e9b\u533a\u95f4\u5462\uff1f<\/p>\n\n\n\n<p>\u6211\u4eec\u662f\u8fd9\u4e48\u5b9a\u4e49\u7684\uff1a<\/p>\n\n\n\n<p>\u5bf9\u4e8e\u67d0\u4e2a\u4f4d\u7f6ex\uff0c\u90a3\u4e48x\u6240\u8986\u76d6\u7684\u533a\u95f4\u91cc\u5143\u7d20\u7684\u4e2a\u6570\u4e3a 2<sup>k<\/sup> \u4e2a\uff08k\u6307\u7684\u662fx\u4e8c\u8fdb\u5236\u672b\u5c3e0\u7684\u6570\u91cf\uff09<\/p>\n\n\n\n<p>\u4f8b\u5982\uff1ax==6\uff0c6\u7684\u4e8c\u8fdb\u5236\u4e3a 110 \u672b\u5c3e0\u7684\u6570\u91cfk=1\uff0c\u6240\u4ee56\u7684\u533a\u95f4\u91cc\u5143\u7d20\u4e2a\u6570\u4e3a\uff1a2<sup>1<\/sup>=2\u4e2a<\/p>\n\n\n\n<p>\u53c8\u5982\uff1ax==8\uff0c8\u7684\u4e8c\u8fdb\u5236\u4e3a 1000 \u672b\u5c3e0\u7684\u6570\u91cfk=3\uff0c\u6240\u4ee58\u7684\u533a\u95f4\u91cc\u5143\u7d20\u7684\u4e2a\u6570\u4e3a\uff1a2<sup>3<\/sup>=8\u4e2a<\/p>\n\n\n\n<p><strong>\u5bf9\u4e8e\u8be2\u95ee\uff1a<\/strong><\/p>\n\n\n\n<p>\u6211\u4eec\u4e00\u822c\u91c7\u7528\u4e8c\u8fdb\u5236\u62c6\u5206\u7684\u65b9\u5f0f\uff0c\u4f8b\u5982\u6211\u4eec\u8981\u8be2\u95ee13\u8fd9\u4e2a\u70b9\u7684\u524d\u7f00\u548c\uff1a<\/p>\n\n\n\n<p>13\u7684\u4e8c\u8fdb\u5236\u4e3a 1101 \uff0c\u6211\u4eec\u6bcf\u6b21\u90fd\u4f1a\u51cf\u53bb\u672b\u5c3e1<\/p>\n\n\n\n<p>1101<sub>2<\/sub> = 13<\/p>\n\n\n\n<p>1100<sub>2<\/sub> = 12\uff081101-0001=1100\uff09<\/p>\n\n\n\n<p>1000<sub>2<\/sub> = 8\uff081100-0100=1000\uff09<\/p>\n\n\n\n<p>\u6211\u4eec\u53ef\u4ee5\u770b\u5230\u4e0a\u9762\u7684\u56fe\uff0c13\u7684\u524d\u7f00\u548c\u7b49\u4e8e\uff1aa[13]+a[12]+a[8]\uff0c\u6b63\u597d\u8ddf\u4e0a\u9762\u64cd\u4f5c\u6240\u5f97\u5230\u7684\u7ed3\u679c\u662f\u4e00\u6837\u7684\u3002<\/p>\n\n\n\n<p><strong>\u5bf9\u4e8e\u4fee\u6539\uff1a<\/strong><\/p>\n\n\n\n<p>\u6211\u4eec\u5c06\u67e5\u8be2\u65f6\u7684\u65b9\u6cd5\u5012\u8fc7\u6765\uff0c\u6bcf\u6b21\u90fd\u5728\u672b\u5c3e1\u7684\u76f8\u540c\u4f4d\u7f6e\u52a0\u4e0a1\uff08\u540c\u4e00\u4e8c\u8fdb\u5236\u4f4d\uff09<\/p>\n\n\n\n<p>\u4f8b\u5982\uff0c\u6211\u4eec\u8981\u4fee\u653910\u8fd9\u4e2a\u70b9\uff1a<\/p>\n\n\n\n<p>1010<sub>2<\/sub>=10<\/p>\n\n\n\n<p>1100<sub>2<\/sub>=12\uff081010+0010=1100\uff09<\/p>\n\n\n\n<p>10000<sub>2<\/sub>=16\uff081100+0100=10000\uff09<\/p>\n\n\n\n<p>\u5bf9\u4e8e10\u8fd9\u4e2a\u70b9\uff0c\u6211\u4eec\u53ea\u9700\u8981\u4fee\u6539\u8282\u70b910\u300112\u300116\uff1b<\/p>\n\n\n\n<p>\u5bf9\u4e8e\u52a0\u51cf\u672b\u5c3e1\u7684\u8fd9\u4e2a\u64cd\u4f5c\uff0c\u6211\u4eec\u662f\u8fd9\u4e48\u5b9e\u73b0\u7684\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int lowbit(int x)\n{\n\treturn x &amp; (-x);\n}\n\/\/x+=lowbit(x)\n\/\/x-=lowbit(x)<\/code><\/pre>\n\n\n\n<p>\u4e3a\u4ec0\u4e48\u8981\u8fd9\u4e48\u5199\u5462\uff1f<\/p>\n\n\n\n<p>\u5728\u8ba1\u7b97\u673a\u91cc\uff0c\u8d1f\u6570\u4e00\u822c\u662f\u7528\u8865\u7801\u8868\u793a\u7684\uff0c\u800c\u8865\u7801\u6307\u5bf9\u539f\u7801\u7684\u6bcf\u4e00\u4f4d\u8fdb\u884c\u53d6\u53cd\uff0c\u7136\u540e\u52a01\uff0c\u6bd4\u5982-6\uff0c6\u7684\u4e8c\u8fdb\u5236\u662f0110\uff0c\u800c\u8865\u7801\u662f 1010\uff080110 \u53d6\u53cd 1001+1=1010\uff09\uff0c\u6211\u4eec\u5bf9\u539f\u7801\u548c\u8865\u7801\u8fdb\u884c\u4e0e\u8fd0\u7b97\uff08&amp;\uff09\u5c31\u4f1a\u5f97\u5230x\u7684\u672b\u5c3e1\uff1b<\/p>\n\n\n\n<p>\u539f\u7801\uff1a0110<\/p>\n\n\n\n<p>\u8865\u7801\uff1a1010<\/p>\n\n\n\n<p>&amp;\uff1a=  0010<\/p>\n\n\n\n<p>\u8fd9\u91cc\u89e3\u91ca\u4e00\u4e0b\uff0c\u6211\u4eec\u521a\u521a\u8bf4\u4e86\uff0c\u8865\u7801\u662f\u5bf9\u539f\u7801\u7684\u6bcf\u4e00\u4f4d\u8fdb\u884c\u53d6\u53cd\uff0c\u8fd9\u65f6\u5019\u8ddf\u539f\u7801\u6b63\u597d\u662f\u53cd\u8fc7\u6765\uff0c\u5982\u679c\u8fd9\u65f6\u5019\u8fdb\u884c&amp;\u8fd0\u7b97\u7ed3\u679c\u4e3a0\uff0c\u56e0\u4e3a\u5b83\u4eec\u6bcf\u4e00\u4f4d\u90fd\u4e0d\u540c\uff1b\u4f46\u5982\u679c\u53d6\u53cd\u4e4b\u540e\u52a01\uff0c\u90a3\u4e48\u5728\u672b\u5c3e\u4e00\u5b9a\u4f1a\u8fdb1\uff0c\u90a3\u4e48\u9664\u8fd9\u4e00\u4f4d\u4ee5\u5916\uff0c\u6240\u6709\u4f4d\u90fd\u90fd\u6ca1\u6709\u76f8\u540c\u76841<\/p>\n\n\n\n<p>\u90a3\u6700\u540e\u770b\u4e00\u4e0b\u4ee3\u7801\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/\u6570\u7ec4a\u662f\u8981\u7ef4\u62a4\u7684\u6570\u7ec4\uff0c\u4e5f\u5c31\u662f\u6811\u72b6\u6570\u7ec4\n\/\/n\u662f\u6570\u7ec4a\u7684\u957f\u5ea6\nint lowbit(int x)\n{\n\treturn x &amp; (-x);\n}\n\nint query(int x)\/\/\u67e5\u8be2\u64cd\u4f5c\n{\n\tint res = 0;\n\twhile (x)\n\t{\n\t\tres += a&#91;x];\n\t\tx -= lowbit(x);\n\t}\n\treturn res;\n}\nvoid add(int x, int v)\/\/x\u8fd9\u4e2a\u4f4d\u7f6e\u52a0\u4e0av\n{\n\twhile (x&lt;=n)\n\t{\n\t\ta&#91;x] += v;\n\t\tx += lowbit(x);\n\t}\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6811\u72b6\u6570\u7ec4\u4e3b\u8981\u662f\u7528\u6765\u89e3\u51b3\u52a8\u6001\u524d\u7f00\u548c\u95ee\u9898\uff1b\u4e00\u822c\u6765\u8bf4\uff0c\u95ee\u9898\u662f\u8fd9\u4e48\u95ee\u7684\uff1a \u7ed9\u5b9a\u4e00\u4e2a\u6570\u7ec4\uff0c\u6709m\u6b21\u64cd\u7eb5\uff08\u9009\u62e9\u6570\u7ec4\u4e2d\u7684\u4e00\u4e2a\u5143 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,20],"tags":[19],"class_list":["post-613","post","type-post","status-publish","format-standard","hentry","category-c-c","category-20","tag-19"],"_links":{"self":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/613","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=613"}],"version-history":[{"count":3,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/613\/revisions"}],"predecessor-version":[{"id":620,"href":"https:\/\/lolife.top\/index.php?rest_route=\/wp\/v2\/posts\/613\/revisions\/620"}],"wp:attachment":[{"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lolife.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}