{"id":44,"date":"2025-11-09T21:07:55","date_gmt":"2025-11-09T13:07:55","guid":{"rendered":"https:\/\/tblog.zeabur.app\/?p=44"},"modified":"2025-11-09T21:07:56","modified_gmt":"2025-11-09T13:07:56","slug":"%e9%a2%98%e8%a7%a3-htoj-p2781-%e3%80%90%e6%a8%a1%e6%9d%bf%e3%80%91%e7%ba%bf%e6%ae%b5%e6%a0%91","status":"publish","type":"post","link":"https:\/\/tblog.zeabur.app\/?p=44","title":{"rendered":"\u9898\u89e3 HTOJ P2781 \u3010\u6a21\u677f\u3011\u7ebf\u6bb5\u6811"},"content":{"rendered":"\n

\u9898\u610f<\/h3>\n\n\n\n

\u5373\u7ef4\u62a4\u4e00\u68f5\u7ebf\u6bb5\u6811\uff0c\u652f\u6301\u5355\u70b9\u4fee\u6539+\u533a\u95f4\u67e5\u8be2\u3002<\/p>\n\n\n\n

\u829d\u58eb\u2014\u2014\u7ebf\u6bb5\u6811<\/h3>\n\n\n\n

\u7ebf\u6bb5\u6811<\/strong>\uff08Segment Tree\uff09\u662f\u4e00\u79cd\u6811\u72b6\u6570\u636e\u7ed3\u6784\uff0c\u4e3b\u8981\u7528\u6765\u9ad8\u6548\u5904\u7406\u533a\u95f4\u67e5\u8be2\uff08RMQ\uff09\u4e0e\u533a\u95f4\u4fee\u6539\u95ee\u9898\u3002<\/p>\n\n\n\n

\u4e0b\u56fe\u5c31\u662f\u4e00\u68f5\u7b80\u5355\u7684\u7ebf\u6bb5\u6811\uff0c\u6bcf\u4e00\u4e2a\u8282\u70b9\u90fd\u662f\u5176\u5b50\u8282\u70b9\u4e4b\u548c\uff0c\u53f6\u5b50\u7ed3\u70b9\u7528\u4e8e\u5b58\u50a8\u6570\u503c\uff0c\u975e\u53f6\u5b50\u7ed3\u70b9\u7528\u4e8e\u7ef4\u62a4\u533a\u95f4\u548c\u3002<\/p>\n\n\n\n

graph TD\n    A[\"[1,4] sum=10\"]-->B[\"[1,2] sum=3\"]\n    A-->C[\"[3,4] sum=7\"]\n    B-->D[\"[1,1] sum=1\"]\n    B-->E[\"[2,2] sum=2\"]\n    C-->F[\"[3,3] sum=3\"]\n    C-->G[\"[4,4] sum=4\"]<\/code><\/pre>\n\n\n\n
\u6211\u4eec\u53ef\u4ee5\u7528\u4e00\u4e2a\u7ed3\u6784\u4f53\u6765\u5b58\u50a8\u7ebf\u6bb5\u6811\uff0c\u4f46\u7531\u4e8e\u4e8c\u53c9\u6811\u7684\u6027\u8d28\uff0c\u5bf9\u4e8e\u7f16\u53f7\u4e3a $n$ \u7684\u8282\u70b9\uff0c\u5176\u5de6\u53f3\u5b50\u8282\u70b9\u5206\u522b\u4e3a $2n$ \u548c $2n+1$\uff0c\u6211\u4eec\u901a\u5e38\u53ef\u4ee5\u7528\u4e00\u4e2a\u6570\u7ec4\u76f4\u63a5\u5b58\u50a8\u7ebf\u6bb5\u6811\uff08\u4e0d\u8fc7\u9700\u8981\u6ce8\u610f\uff0c\u7531\u4e8e\u7ebf\u6bb5\u6811\u9700\u8981\u7ef4\u62a4\u533a\u95f4\u548c\uff0c\u6240\u4ee5\u901a\u5e38\u8981\u5f00 $4$ \u500d\u7a7a\u95f4\uff0c\u5982\u679c\u4f60\u60f3\u7701\u7a7a\u95f4\u800c\u4e0d\u5f00 $4$ \u500d\uff0c\u5c31\u7b49\u7740 RE \u5427 doge\uff09\u3002<\/p>\n\n\n\n
\u7531\u4e8e\u7ebf\u6bb5\u6811\u662f\u57fa\u4e8e\u5206\u6cbb\u601d\u60f3\u5b9e\u73b0\u7684\uff0c\u6240\u4ee5\u53ef\u4ee5\u628a\u5355\u6b21\u67e5\u8be2\u6216\u4fee\u6539\u7684\u590d\u6742\u5ea6\u964d\u5230 $\\mathcal{O}(\\log n)$\u3002<\/p>\n\n\n\n
\u603b\u65f6\u95f4\u590d\u6742\u5ea6\uff1a$\\mathcal{O}(m\\log n)$\u3002<\/p>\n\n\n\n
\u6807\u7a0b<\/h3>\n\n\n\n
#include<bits\/stdc++.h>\n#define int long long\nusing namespace std;\nint tree[800005],a[200005];\/\/\u6811\u8981\u5f00 4 \u500d\ninline void push_up(int id)\/\/\u4e0a\u4f20\uff0c\u6ce8\u610f\u4e0d\u8981\u548clazy_tag\u7684\u4e0b\u4f20\u641e\u6df7\n{\n    tree[id]=tree[id<<1]+tree[id<<1|1];\/\/\u66f4\u65b0\u7236\u8282\u70b9\u4e3a\u5b50\u8282\u70b9\u4e4b\u548c\n}\ninline void build(int id,int l,int r)\/\/\u5efa\u6811\n{\n    if(l==r)\/\/\u5230\u53f6\u5b50\u8282\u70b9\u4e86\n    {\n        tree[id]=a[l];\/\/\u8d4b\u503c\n        return ;\n    }\n    else\n    {\n        int mid=l+r>>1;\/\/\u5206\u6cbb\n        build(id<<1,l,mid);\n        build(id<<1|1,mid+1,r);\n        push_up(id);\n        return ;\n    }\n}\ninline int query(int id,int l,int r,int L,int R)\/\/\u533a\u95f4\u67e5\u8be2\n{\n    if(L<=l&&R>=r)return tree[id];\/\/\u5b8c\u5168\u5305\u542b\n    int mid=l+r>>1;\n    int ans=0;\n    if(L<=mid)ans+=query(id<<1,l,mid,L,R);\/\/\u641c\u5de6\u5b50\u6811\n    if(R>mid)ans+=query(id<<1|1,mid+1,r,L,R);\/\/\u53f3\u5b50\u6811\n    return ans;\n}\ninline void update(int id,int l,int r,int pos,int x)\/\/\u5355\u70b9\u4fee\u6539\n{\n    if(l==r)\n    {\n        tree[id]=x;\n        return;\n    }\n    int mid=l+r>>1;\n    if(pos<=mid)update(id<<1,l,mid,pos,x);\n    else update(id<<1|1,mid+1,r,pos,x);\n    push_up(id);\n}\nsigned main() \n{\n    int n,m;\n    cin>>n>>m;\n    for(int i=1;i<=n;i++)\n    {\n        cin>>a[i];\n    }\n    build(1,1,n);\/\/\u9664\u975e\u52a8\u6001\u5f00\u70b9\uff0c\u5426\u5219\u90fd\u8981\u5efa\u6811\n    while(m--)\n    {\n        int op,l,r;\n        cin>>op>>l>>r;\n        if(op==1)\n        {\n            update(1,1,n,l,r);\n        }\n        else if(op==2)\n        {\n            cout<<query(1,1,n,l,r)<<endl;\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u610f \u5373\u7ef4\u62a4\u4e00\u68f5\u7ebf\u6bb5\u6811\uff0c\u652f\u6301\u5355\u70b9\u4fee\u6539+\u533a\u95f4\u67e5\u8be2\u3002 \u829d\u58eb\u2014\u2014\u7ebf\u6bb5\u6811 \u7ebf\u6bb5\u6811\uff08Segment Tree\uff09\u662f\u4e00\u79cd\u6811\u72b6 […]<\/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":[3],"class_list":["post-44","post","type-post","status-publish","format-standard","hentry","category-oi","tag-oi"],"featured_image_src":null,"author_info":{"display_name":"CaelumRadish_c","author_link":"https:\/\/tblog.zeabur.app\/?author=1"},"_links":{"self":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/44","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=44"}],"version-history":[{"count":1,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/44\/revisions"}],"predecessor-version":[{"id":45,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=\/wp\/v2\/posts\/44\/revisions\/45"}],"wp:attachment":[{"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=44"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=44"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tblog.zeabur.app\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}