{"id":181,"date":"2020-04-04T20:59:09","date_gmt":"2020-04-04T12:59:09","guid":{"rendered":"http:\/\/47.103.223.234:100\/?p=181"},"modified":"2020-04-26T17:32:16","modified_gmt":"2020-04-26T09:32:16","slug":"%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/04\/04\/%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84\/","title":{"rendered":"\u6811\u72b6\u6570\u7ec4"},"content":{"rendered":"<h2>\u6811\u72b6\u6570\u7ec4<\/h2>\n<p>\u5148\u6765\u4ecb\u7ecd\u6811\u72b6\u6570\u7ec4\u7684\u8fd0\u4f5c\u65b9\u5f0f\uff0c\u8bbe\u539f\u6709\u6570\u7ec4\u4e3aA\uff0c\u73b0\u5728\u6211\u4eec\u8981\u505a\u7684\u65f6\u5bf9A\u7684\u67d0\u4e2a\u533a\u95f4\u8fdb\u884c\u6c42\u77e5(\u6c42\u548c\uff0c\u6700\u5927\u6700\u5c0f\u503c\uff0c\u6216\u5176\u4ed6)\uff0c\u4ee5\u53ca\u5bf9\u67d0\u4e2a\u5355\u70b9\u8fdb\u884c\u4fee\u6539\uff0c\u6216\u67d0\u4e2a\u533a\u95f4\u8fdb\u884c\u4fee\u6539\u7b49\u7b49\u64cd\u4f5c\uff0c\u5728\u7528\u6734\u7d20\u7b97\u6cd5\u65f6\u4f1a\u6d88\u8017\u5927\u91cf\u65f6\u95f4\uff0c\u7528\u6811\u72b6\u6570\u7ec4\u548c\u7ebf\u6bb5\u6811\u53ef\u4ee5\u5728\u77ed\u65f6\u95f4\u5185\u89e3\u51b3\u95ee\u9898\uff0c\u6811\u72b6\u6570\u7ec4\u53ef\u4ee5\u89e3\u51b3\u7684\u95ee\u9898\uff0c\u7ebf\u6bb5\u6811\u90fd\u53ef\u4ee5\u89e3\u51b3\uff0c\u4f46\u6784\u9020\u7ebf\u6bb5\u6811\u4f1a\u6d88\u8017\u5f88\u591a\u65f6\u95f4\uff0c\u5bf9\u4e8e\u5927\u591a\u6570\u533a\u95f4\u64cd\u4f5c\u9898\u76ee\uff0c\u4f7f\u7528\u6811\u72b6\u6570\u7ec4\u53ef\u4ee5\u66f4\u5feb\u7684\u89e3\u51b3\u95ee\u9898\uff0c\u800c\u4e14\u4ee3\u7801\u4e5f\u5f88\u5c11\u3002\uff0c\uff0c\uff0c\uff0c\u4f46\u662f\u76f8\u5bf9\u6765\u8bf4\u529f\u80fd\u8fd8\u662f\u53d7\u5230\u9650\u5236\u7684\u3002<\/p>\n<p>\u6811\u72b6\u6570\u7ec4C\u4e2dC[i]\u7684\u503c\u4e3a\u4ee5i\u7ed3\u5c3e\u7684lowbit(i)\u4e2a\u957f\u5ea6\u7684\u533a\u95f4\u5185\u7684\u76ee\u6807\u503c(\u6c42\u548c\uff0c\u6700\u5927\u6700\u5c0f\u503c\uff0c\u6216\u5176\u4ed6)\uff0c\u90a3\u4e48\u6211\u4eec\u8981\u6c42\u4ecei\u52300\u4e4b\u95f4\u7684\u6240\u6709\u6570\u7684\u548c\uff0c\u53ea\u9700\u8981\u8ba1\u7b97\u5f53\u524d\u7684C[i]\u503c\uff0c\u7136\u540e\u4e00\u76f4\u51cf\u53bblowbit(i)\u5373\u53ef\u3002\u4e00\u4e2a\u5f88\u5927\u7684\u6570\u4e5f\u53ef\u4ee5\u5728logn\u6b21lowbit\u5185\u8868\u793a\u51fa\u6765\u3002lowbit(i)\u7684\u503c\u4e3ai\u7684\u4e8c\u8fdb\u5236\u6570\u4e2d\uff0c\u4ece\u4f4e\u4f4d\u5230\u9ad8\u4f4d\uff0c\u7b2c\u4e00\u4e2a\u8fde\u7eed0\u7684\u4e2a\u6570\uff0clowbit(i) = <code class=\"katex-inline\">2^k<\/code>\uff0ck = \u7b2c\u4e00\u4e2a\u8fde\u7eed0\u7684\u4e2a\u6570\u3002\u6bd4\u5982i=18=10010(2)\u7684\u7b2c\u4e00\u4e2a\u8fde\u7eed0\u7684\u4e2a\u6570\u4e3a1\uff0c\u800c\u4e0d\u662f2\uff0c\u5219lowbit(i) = 2\u3002<\/p>\n<p>\u8bbeA\u4e3a\u539f\u59cb\u6570\u7ec4\uff0cC\u4e3a\u6811\u72b6\u6570\u7ec4\u3002<br \/>\nC[1] = A[1];<br \/>\nC[2] = A[2] + A[1];<br \/>\nC[3] = A[3];<br \/>\nC[4] = A[4] + A[3] + A[2] + A[1];<br \/>\nC[5] = A[5];<br \/>\nC[6] = A[6] + A[5];<br \/>\nC[7] = A[7];<br \/>\nC[8] = A[8] + A[7] +...+ A[2] + A[1];<br \/>\n\u5373<strong>C[i]\u6240\u8986\u76d6\u7684\u533a\u95f4\u4e3a\u4ee5i\u7ed3\u5c3e\u7684\u957f\u5ea6\u4e3alowbit\u7684\u533a\u95f4<\/strong>\uff0c\u82e5\u6211\u4eec\u73b0\u5728\u8981\u8ba1\u7b97sum(A[1]-A[7])\uff0c\u90a3\u4e48i\u4ece7\u5f00\u59cb\uff0c\u5148\u52a0\u4e0aC[7]\uff0c\u7136\u540ei -= lowbit(i)\uff0c\u6b64\u65f6i=6\uff0c\u52a0\u4e0aC[6]\uff0c\u518d\u51cf\u53bblowbit(i)\uff0c\u6b64\u65f6i\u4e3a4\uff0c\u52a0\u4e0aC[4]\uff0c\u51cf\u53bblowbit7(i)\u540e\uff0ci\u4e3a0\uff0c\u8ba1\u7b97\u7ed3\u675f\uff0cA[1]-A[7]\u5185\u7684\u6570\u90fd\u53ea\u88ab\u8ba1\u7b97\u4e86\u4e00\u6b21\u3002<br \/>\n\u5728\u4e0a\u8ff0\u8ba1\u7b97\u8fc7\u7a0b\u4e2d\uff0c\u5171\u8fed\u4ee3\u4e863\u6b21\uff0c7\uff0c6\uff0c4\uff0c\u7136\u540e\u5c31\u662f0\u4e86\u3002\u90a3\u5f53\u6211\u4eec\u8981\u8ba1\u7b97\u4e00\u4e2a\u5f88\u5927\u7684\u6570\u65f6\uff0c\u6bd4\u5982100w\uff0c\u8fed\u4ee3\u7684\u6b21\u6570\u4f1a\u4e0d\u4f1a\u5f88\u5927\u5462\uff1f\u5f53\u7136\u4e0d\u4f1a\uff0c\u518d\u5927\u4e5f\u4f1a\u5728logn\u6b21\u5185\u5b8c\u6210\u8fed\u4ee3\u3002<br \/>\n\u6211\u4eec\u6765\u5206\u6790\u4e00\u4e0b\u5177\u4f53\u7684\u8fed\u4ee3\u8fc7\u7a0b\uff0c\u5728\u4e0a\u8ff0i=7\u65f6\uff0c7\u7684\u4e8c\u8fdb\u5236\u6570\u4e3a111\uff0ci = <code class=\"katex-inline\">2^2+2^1+2^0<\/code>\uff0c\u800c\u5728\u8fed\u4ee3\u8fc7\u7a0b\u4e2d\uff0c\u6211\u4eec\u53d1\u73b0\u4e09\u6b21lowbit(i)\u7684\u503c\u6070\u597d\u5c31\u662f<code class=\"katex-inline\">2^0\u30012^1\u30012^2<\/code>\uff0c\u8fd9\u5c31\u662f\u6811\u72b6\u6570\u7ec4\u7684\u795e\u5947\u4e4b\u5904\uff0c\u5229\u7528\u4e8c\u8fdb\u5236\u6570\u5efa\u7acb\u8d77\u6765\u7684\u3002\u90a3\u6211\u4eec\u77e5\u9053\u4efb\u4f55\u4e00\u4e2a\u6b63\u6574\u6570\u90fd\u53ef\u4ee5\u552f\u4e00\u8868\u793a\u6210\u4e00\u4e9b2\u7684\u5e42\u7684\u548c\uff0c\u4e14\u8fd9\u4e9b\u5e42\u7684\u4e2a\u6570\u4e00\u5b9a\u4e0d\u4f1a\u8d85\u8fc7logn(\u4ece\u4e8c\u8fdb\u5236\u6570\u770b\uff0c\u6700\u591a\u4e5f\u5c31logn\u4e2a1)\u3002\u56e0\u6b64\u4f7f\u7528\u6811\u72b6\u6570\u7ec4\u53ef\u4ee5\u5f88\u5feb\u7684\u6c42\u89e3\u533a\u95f4\u95ee\u9898\u3002\u65f6\u95f4\u590d\u6742\u5ea6O(logn)\uff0c\u76f8\u6bd4\u7ebf\u6bb5\u6811\uff0c\u6811\u72b6\u6570\u7ec4\u6784\u9020\u8d77\u6765\u7b80\u5355\uff0c\u4e14\u9ad8\u6548\u3002<\/p>\n<h4>\u6784\u9020\u6700\u7b80\u5355\u7684\u6811\u72b6\u6570\u7ec4<\/h4>\n<p>\u8bbe\u6570\u7ec4c\uff0cc[i]\u7684\u503c\u4e3a\u4ee5i\u7ed3\u5c3e\u7684lowbit(i)\u4e2a\u957f\u5ea6\u7684\u533a\u95f4\u5185\u7684\u76ee\u6807\u503c(\u6c42\u548c\uff0c\u6700\u5927\u6700\u5c0f\u503c\uff0c\u6216\u5176\u4ed6)\uff0c\u82e5\u8981\u4f1a\u7528\u4ec5\u4ec5\u77e5\u9053\u8fd9\u4e2a\u5c31\u591f\u4e86\u3002<br \/>\n\u5bf9\u4e8e\u67d0\u4e2a\u70b9i\uff0c\u5305\u542bi\u7684\u70b9\u6709i,i+lowbit(i),i+lowbit(i)+lowbit(i+lowbit(i))+lowbit(..)\u4e00\u76f4\u9012\u5f52\u4e0b\u53bb\uff0c\u76f4\u81f3\u6700\u53f3\u7aef\u3002  lowbit(i) = i&amp;(-i);<br \/>\n\u6240\u4ee5\u518d\u6784\u9020\u6811\u72b6\u6570\u7ec4\u65f6\uff0c\u4ee3\u7801\u5f88\u7b80\u5355\u3002<\/p>\n<pre><code class=\"language-c++\">void update(int i,int k,int N){     \/\/k\u4e3a\u8981\u4fee\u6539\u7684\u503c\uff0c\u53ef\u6b63\u53ef\u8d1f\n    while (i&lt;=N){\n        c[i] += k;\n        i += lowbit(i);\n    }\n    return;\n}<\/code><\/pre>\n<p>\u6c421-i\u533a\u95f4\u5185\u7684\u548c,,\u8fd9\u91cc\u8981\u5145\u5206\u7406\u89e3c[i]\u7684\u4f5c\u7528\u8303\u56f4\u662f\u4ee5i\u7ed3\u5c3e\u7684\uff0c\u957f\u5ea6\u4e3alowbit(i)\u7684\u533a\u95f4\u3002<\/p>\n<pre><code class=\"language-c++\">int query(int i){\n    int ans = 0;\n    while (i){\n        ans += c[i];\n        i -= lowbit(i);\n    }\n    return ans;\n}<\/code><\/pre>\n<p>\u6a21\u677f\u9898 <a href=\"http:\/\/acm.hdu.edu.cn\/showproblem.php?pid=1166\">HUD1166<\/a><br \/>\n\u9898\u610f\uff1a\u7ed9\u51faN\u4e2a\u6570\uff0c\u6bcf\u6b21\u64cd\u4f5c\u6709\u589e\u52a0\u67d0\u4e2a\u70b9\u7684\u503c\uff0c\u51cf\u5c11\u67d0\u4e2a\u70b9\u7684\u503c\uff0c\u6c42\u67d0\u4e2a\u533a\u95f4\u5185\u7684\u548c\u3002<\/p>\n<pre><code class=\"language-c++\">#include &lt;cstdio&gt;\n#include &lt;cstring&gt;\nusing namespace std;\nconst int maxn = 5e4+5;\nint c[maxn];\nchar s[20];\ninline int lowbit(int i){return i&amp;(-i);}\nvoid update(int i,int k,int N);\nint query(int i);\nint main(){\n    int T,N,cases = 0,temp,x,y;\n    scanf (&quot;%d&quot;,&amp;T);\n    while (T--){\n        printf (&quot;Case %d:\\n&quot;,++cases);\n        memset(c,0,sizeof c);\n        scanf (&quot;%d&quot;,&amp;N);\n        for (int i=1;i&lt;=N;i++){\n            scanf (&quot;%d&quot;,&amp;temp);\n            update(i,temp,N);\n        }\n        while (1){\n            scanf (&quot;%s&quot;,s+1);\n            if (s[1]==&#039;E&#039;)  break;\n            scanf (&quot;%d %d&quot;,&amp;x,&amp;y);\n            if (s[1]==&#039;A&#039;)  update(x,y,N);\n            else if (s[1]==&#039;S&#039;) update(x,-y,N);\n            else    printf (&quot;%d\\n&quot;,query(y)-query(x-1));\n        }\n    }\n    return 0;\n}\nvoid update(int i,int k,int N){\n    while (i&lt;=N){\n        c[i] += k;\n        i += lowbit(i);\n    }\n    return;\n}\nint query(int i){\n    int ans = 0;\n    while (i){\n        ans += c[i];\n        i -= lowbit(i);\n    }\n    return ans;\n}<\/code><\/pre>\n<p>\u63a5\u4e0b\u6765\u8ba8\u8bba\u8f83\u590d\u6742\u7684\u95ee\u9898<br \/>\n\u5bf9\u4e8e\u533a\u95f4\u7684\u64cd\u4f5c\u5927\u81f4\u53ef\u5206\u4e3a4\u5927\u7c7b\u3002<\/p>\n<blockquote>\n<p><strong><em>1.\u5355\u70b9\u66f4\u65b0\uff0c\u5355\u70b9\u67e5\u8be2<br \/>\n2.\u5355\u70b9\u66f4\u65b0\uff0c\u533a\u95f4\u67e5\u8be2<br \/>\n3.\u533a\u95f4\u66f4\u65b0\uff0c\u5355\u70b9\u67e5\u8be2<br \/>\n4.\u533a\u95f4\u66f4\u65b0\uff0c\u533a\u95f4\u67e5\u8be2<\/em><\/strong><\/p>\n<\/blockquote>\n<p>\u5176\u4e2d1\u7528\u4f20\u7edf\u6570\u7ec4\u5c31\u53ef\u89e3\u51b3\uff0c2\u4e0a\u9762\u5df2\u7ecf\u8ba8\u8bba\u3002\u4e0b\u9762\u770b3\uff0c4<\/p>\n<h4>\u533a\u95f4\u66f4\u65b0\uff0c\u5355\u70b9\u67e5\u8be2<\/h4>\n<p>\u5728\u539f\u6570\u7ec4A\u7684\u57fa\u7840\u4e0a\uff0c\u6784\u5efa\u4e00\u4e2a\u5dee\u5206\u6570\u7ec4D\uff0cD[i] = A[i]-A[i-1]\uff0c\u90a3\u4e48\uff0cA[i]\u7684\u503c\u5c31\u662fD\u6570\u7ec4\u7684\u524di\u4e2a\u6570\u7684\u548c\uff0c\u6211\u4eec\u5728D\u6570\u7ec4\u4e0a\u5efa\u7acb\u6811\u72b6\u6570\u7ec4\u5373\u53ef\u3002\u5bf9\u4e8e\u6bcf\u6b21\u66f4\u65b0\uff0c\u4f8b\u5982\u5728[x,y]\u533a\u95f4\u5185\u52a0\u51cf\u4e00\u4e2a\u5e38\u6570\u503c\uff0cD[x+1~y]\u7684\u503c\u662f\u4e0d\u53d8\u7684\uff0c\u53ea\u9700\u66f4\u6539D[x]\u548cD[y+1]\u7684\u503c\u5c31\u597d\u3002<br \/>\n\u90a3\u4e48\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u6811\u72b6\u6570\u7ec4c\u662f\u5efa\u7acb\u5728\u5dee\u5206\u6570\u7ec4D\u4e0a\u7684\uff0c\u6bcf\u6b21\u66f4\u65b0\u533a\u95f4\u503c\uff0c\u8981\u66f4\u65b0D[x]\u548cD[y+1]\u7684\u503c\u3002\u4ee3\u7801\u4e0e\u7b2c2\u79cd\u60c5\u51b5\u7684\u5b8c\u5168\u76f8\u540c\u3002<br \/>\n\u6bcf\u6b21\u66f4\u65b0\u548c\u67e5\u8be2\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u4e3aO(logn).<\/p>\n<pre><code class=\"language-c++\">for (rint i=1;i&lt;=N;i++){\n        scanf (&quot;%d&quot;,&amp;A[i]);\n        D[i] = A[i] - A[i-1];\n        update(i,D[i]);\n    }\n    \/\/\u53ea\u662f\u539f\u6570\u7ec4\u4eceA[]\u53d8\u6210\u4e86\u5dee\u5206\u6570\u7ec4D[]\uff0cupdae\u548cquery\u51fd\u6570\u548c\u4e0a\u9762\u4e00\u6a21\u4e00\u6837<\/code><\/pre>\n<h4>\u533a\u95f4\u66f4\u65b0\uff0c\u533a\u95f4\u67e5\u8be2<\/h4>\n<p>\u57283\u4e2d\uff0c\u6211\u4eec\u77e5\u9053\u67e5\u8be2\u6570\u7ec4A\u4e2d\u5355\u70b9\u503c\u65f6\uff0c\u662f\u5dee\u5206\u6570\u7ec4\u76841-i\u7684\u548c\uff0c\u90a3\u8981\u67e5\u8be2\u6570\u7ec4A\u7684\u524di\u4e2a\u6570\u7684\u548c\u5462\uff1f\u5f53\u7136\u5c31\u662f\u5dee\u5206\u6570\u7ec4D\u4e2d\u524di\u7684\u6570\u7684\u6240\u6709\u524d\u7f00\u548c\u7684\u548c\u3002\u90a3\u4e48\u6700\u540e\u7b97\u4e0b\u6765\uff0cD[1]\u88ab\u52a0\u4e86i\u6b21\uff0cD[2]\u88ab\u52a0\u4e86i-1\u6b21...D[i]\u88ab\u52a0\u4e861\u6b21\u3002<br \/>\n\u53ef\u4ee5\u8fdb\u884c\u5982\u4e0b\u8868\u793a<br \/>\n<code class=\"katex-inline\">A[1]+A[2]+...+A[i] =D[1]*i+D[2]*(i-1)+...+D[i]*1<\/code><br \/>\n<code class=\"katex-inline\">= (D[1]+D[2]+...+D[i])*i-(D[1]*0+D[2]*1+...D[i]*(i-1))<\/code><br \/>\n\u5373\u6211\u4eec\u8fd8\u9700\u8981\u518d\u5efa\u7acb\u4e00\u4e2a\u6811\u72b6\u6570\u7ec4C2[]\uff0c\u76ee\u6807\u503c\u4e3a<code class=\"katex-inline\">D[i]*(i-1)<\/code>.<br \/>\nupdate\u51fd\u6570\u9700\u8981\u66f4\u65b0\u4e00\u4e0b<\/p>\n<pre><code class=\"language-c++\">void update(int i,ll k){\n    ll temp = k*(i-1);\n    while (i&lt;=N){\n        c1[i] += k;\n        c2[i] += temp;\n        i += lowbit(i);\n    }\n    return;\n}<\/code><\/pre>\n<p>\u62ff\u6765\u4e24\u9053\u677f\u5b50\u9898<br \/>\n<a href=\"https:\/\/www.luogu.com.cn\/problem\/P3368\">\u6d1b\u8c37P3368<\/a> \u533a\u95f4\u66f4\u65b0\uff0c\u5355\u70b9\u67e5\u8be2<br \/>\n<a href=\"http:\/\/poj.org\/problem?id=3468\">POJ3468<\/a>  \u533a\u95f4\u66f4\u65b0\uff0c\u533a\u95f4\u67e5\u8be2<\/p>\n<p><a href=\"https:\/\/www.luogu.com.cn\/problem\/P3368\">\u6d1b\u8c37P3368<\/a> \u533a\u95f4\u66f4\u65b0\uff0c\u5355\u70b9\u67e5\u8be2<br \/>\ninline\u6548\u679c\u633a\u660e\u663e\u7684\uff0cregister int\u7528\u4e86\u53cd\u5012\u6162\u4e86\u4e00\u4e9b\uff1f\uff1f<\/p>\n<pre><code class=\"language-c++\">#include &lt;cstdio&gt;\n#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n#define rint register int\nconst int maxn = 5e5+5;\nint A[maxn],D[maxn],c[maxn];\nint N,M;\ninline int lowbit(int i){return i&amp;(-i);}\ninline void update(int i,int k){\n    while (i&lt;=N){\n        c[i] += k;\n        i += lowbit(i);\n    }\n    return;\n}\ninline int query(int i){\n    int ans = 0;\n    while (i){\n        ans += c[i];\n        i -= lowbit(i);\n    }\n    return ans;\n}\nint main(){\n    int x,y,k,flag;\n    scanf (&quot;%d %d&quot;,&amp;N,&amp;M);\n    for (rint i=1;i&lt;=N;i++){\n        scanf (&quot;%d&quot;,&amp;A[i]);\n        D[i] = A[i] - A[i-1];\n        update(i,D[i]);\n    }\n    while (M--){\n        scanf (&quot;%d&quot;,&amp;flag);\n        if (flag==1){\n            scanf (&quot;%d%d%d&quot;,&amp;x,&amp;y,&amp;k);\n            D[x] += k,D[y+1] -= k;\n            update(x,k);    update(y+1,-k);\n            continue;\n        }\n        scanf (&quot;%d&quot;,&amp;x);\n        printf (&quot;%d\\n&quot;,query(x));\n    }\n    return 0;\n}<\/code><\/pre>\n<p><a href=\"http:\/\/poj.org\/problem?id=3468\">POJ3468<\/a>  \u533a\u95f4\u66f4\u65b0\uff0c\u533a\u95f4\u67e5\u8be2<\/p>\n<pre><code class=\"language-c++\">#include &lt;cstdio&gt;\n#include &lt;iostream&gt;\nusing namespace std;\ntypedef long long ll;\nconst int maxn = 1e5+5;\nll a1[maxn],D[maxn],c1[maxn],c2[maxn];\nint N,Q;\n\ninline int lowbit(int i){return i&amp;(-i);}\ninline void update(int i,ll k);\ninline ll GetSum1(int i);\ninline ll GetSum2(int i);\nint main(){\n    char ch;\n    int a,b,c;\n    scanf (&quot;%d %d&quot;,&amp;N,&amp;Q);\n    for (int i=1;i&lt;=N;i++){\n        scanf (&quot;%lld&quot;,&amp;a1[i]);     D[i] = a1[i] - a1[i-1];\n        update(i,D[i]);\n    }\n    while (Q--){\n        cin &gt;&gt; ch;\n        if (ch==&#039;C&#039;){\n            scanf (&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c);\n            D[a] += c,D[b+1] -= c;\n            update(a,c);\n            update(b+1,-c);\n            continue;\n        }\n        scanf (&quot;%d %d&quot;,&amp;a,&amp;b);\n        printf (&quot;%lld\\n&quot;,GetSum1(b)*b-GetSum2(b)-GetSum1(a-1)*(a-1)+GetSum2(a-1));\n    }\n    return 0;\n}\nll GetSum2(int i){\n    ll ans = 0;\n    while (i){\n        ans += c2[i];\n        i -= lowbit(i);\n    }\n    return ans;\n}\nll GetSum1(int i){\n    ll ans = 0;\n    while (i){\n        ans += c1[i];\n        i -= lowbit(i);\n    }\n    return ans;\n}\nvoid update(int i,ll k){\n    ll temp = k*(i-1);\n    while (i&lt;=N){\n        c1[i] += k;\n        c2[i] += temp;\n        i += lowbit(i);\n    }\n    return;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6811\u72b6\u6570\u7ec4 \u5148\u6765\u4ecb\u7ecd\u6811\u72b6\u6570\u7ec4\u7684\u8fd0\u4f5c\u65b9\u5f0f\uff0c\u8bbe\u539f\u6709\u6570\u7ec4\u4e3aA\uff0c\u73b0\u5728\u6211\u4eec\u8981\u505a\u7684\u65f6\u5bf9A\u7684\u67d0\u4e2a\u533a\u95f4\u8fdb\u884c\u6c42\u77e5(\u6c42\u548c\uff0c [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[37],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/181"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=181"}],"version-history":[{"count":16,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/181\/revisions"}],"predecessor-version":[{"id":221,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/181\/revisions\/221"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=181"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=181"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}