{"id":37,"date":"2023-01-31T20:19:25","date_gmt":"2023-01-31T12:19:25","guid":{"rendered":"https:\/\/solost.cn\/?p=37"},"modified":"2023-01-31T20:19:25","modified_gmt":"2023-01-31T12:19:25","slug":"74","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=37","title":{"rendered":"\u6811\u72b6\u6570\u7ec4"},"content":{"rendered":"

\u6811\u72b6\u6570\u7ec4\u7b14\u8bb0<\/h1>\n

\u6811\u72b6\u6570\u7ec4\u529f\u80fd<\/h2>\n
    \n
  1. \u5feb\u901f\u6c42\u524d\u7f00\u548cO(long)<\/code><\/li>\n
  2. \u4fee\u6539\u67d0\u4e00\u4e2a\u6570O(logn)<\/code><\/li>\n<\/ol>\n

    \u539f\u7406<\/h2>\n

    \u57fa\u4e8e\u4e8c\u8fdb\u5236\uff0c$x = 2^{i_k} + 2^{i_{k-1}} + .... + 2^{i_1}$<\/p>\n

    $i_k >= i_{k-1} >= ....i_1\uff0c k <= logx$<\/p>\n

    \u90a3\u4e481~x\u5c31\u53ef\u4ee5\u5199\u6210\u8fd9\u4e9b\u533a\u95f4<\/p>\n

    \u64cd\u4f5c<\/h2>\n
      \n
    1. \u4fee\u6539\u64cd\u4f5c\uff1afor(int i = x; i <= n; i += lowbit(i)) tree[i] += c<\/code><\/li>\n
    2. \u67e5\u8be2\u64cd\u4f5c\uff1afor(int i = x; i; i -= lowbit(i)) res += tree[i]<\/code><\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

      \u6811\u72b6\u6570\u7ec4\u7b14\u8bb0 \u6811\u72b6\u6570\u7ec4\u529f\u80fd \u5feb\u901f\u6c42\u524d\u7f00\u548cO(long) \u4fee\u6539\u67d0\u4e00\u4e2a\u6570O(logn) \u539f\u7406 \u57fa\u4e8e\u4e8c\u8fdb\u5236\uff0c$x = 2^{i_k} + 2^{i_{k-1}} + .... + 2^{i_1}$ $i_k >= i_{k-1} >= ....i_1\uff0c k <= logx$ \u90a3\u4e481~x\u5c31\u53ef\u4ee5\u5199\u6210\u8fd9\u4e9b\u533a\u95f4 \u64cd\u4f5c \u4fee\u6539\u64cd\u4f5c\uff1afor(int i = x; i <= n; i += lowbit(i)) tree[i] += c \u67e5\u8be2\u64cd\u4f5c\uff1afor(int i = x; i; i -= lowbit(i)) res += tree[i]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72],"tags":[],"class_list":["post-37","post","type-post","status-publish","format-standard","hentry","category-acm"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/37","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=37"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/37\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=37"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=37"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}