{"id":197,"date":"2019-08-13T11:42:33","date_gmt":"2019-08-13T03:42:33","guid":{"rendered":"https:\/\/blog.chtholly.moe\/?p=197"},"modified":"2021-08-21T18:13:29","modified_gmt":"2021-08-21T10:13:29","slug":"%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=197","title":{"rendered":"\u6811\u72b6\u6570\u7ec4"},"content":{"rendered":"<h1>\u6811\u72b6\u6570\u7ec4\u6700\u6838\u5fc3\u7684\u90e8\u5206\uff0c\u4fbf\u662flowbit()<\/h1>\n<pre>int lowbit(int x){return x ^ (-x);}<\/pre>\n<p>\u5b83\u7684\u4f5c\u7528\u662f\u8fd4\u56dex\u5728\u4e8c\u8fdb\u5236\u4e0b\u6700\u4f4e\u4f4d\u76841\u6240\u5bf9\u5e94\u7684\u503c<\/p>\n<p>\u5373\u8ba1\u7b972^k\u7684\u503c<\/p>\n<p>\u5728\u6811\u72b6\u6570\u7ec4\u4e2d\uff0c\u5b83\u6070\u597d\u8fd4\u56de\u5f53\u524d\u8282\u70b9\u6240\u6307\u7684\u4e0b\u4e00\u4e2a\u4e2d\u7ee7\u8282\u70b9(\u5373\u5b58\u50a8\u533a\u95f4\u548c\u7684\u8282\u70b9)<\/p>\n<p>\u8fd8\u6709\u4e00\u4e2a\u91cd\u8981\u7684\u95ee\u9898\uff0c\u67e5\u8be2\u4e0e\u4fee\u6539\u65f6\uff0c\u65b9\u5411\u4e0d\u80fd\u9519<\/p>\n<pre>int query(int loc){\/\/\u67e5\u8be2\u5411\u4e0b\u67e5\u8be2\r\n    long long ans=0;\r\n    for(int i=loc;i&gt;0;i-=lowbit(i)){\r\n        ans+=C[i];\r\n    }\r\n    retrun ans;\r\n}\r\nvoid add(int loc,int x){\/\/\u4fee\u6539\u5219\u662f\u5bf9\u5b83\u540e\u7ee7\u7684\u4e2d\u7ee7\u8282\u70b9\u6709\u5f71\u54cd\uff0c\u5411\u4e0a\u66f4\u65b0\r\n    for(int i=loc;i&lt;=n;i+=lowbit(i)){\r\n        C[i]+=x;\r\n    }\r\n}<\/pre>\n<p>\u6700\u540e\u662f\u5efa\u6811\u3002\u8bbeC[i]\u4e3a\u6811\u72b6\u6570\u7ec4\u4e2d\u7684\u7b2ci\u9879\uff0cA[i]\u5b58\u50a8\u539f\u5e8f\u5217\u7684\u7b2ci\u9879<\/p>\n<p>\u5219\u6709C[i] = A(i \u2013 2^k + 1) + &#8230; + A[i]<\/p>\n<pre>void build(){\r\n     for(int i=1;i&lt;=n;i++)\/\/\u679a\u4e3eC[i]\r\n        for(int j=i-lowbit(i)+1;j&lt;=i;j++)\/\/\u4ecei-2^k+1\u7d2f\u52a0\u5230i\r\n            C[i]+=A[j];\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6811\u72b6\u6570\u7ec4\u6700\u6838\u5fc3\u7684\u90e8\u5206\uff0c\u4fbf\u662flowbit() int lowbit(int x){return x ^ (-x) [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-197","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/197","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=197"}],"version-history":[{"count":4,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/197\/revisions"}],"predecessor-version":[{"id":211,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/197\/revisions\/211"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=197"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=197"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=197"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}