{"id":122,"date":"2023-04-10T22:15:22","date_gmt":"2023-04-10T14:15:22","guid":{"rendered":"https:\/\/solost.cn\/?p=122"},"modified":"2023-04-10T22:15:22","modified_gmt":"2023-04-10T14:15:22","slug":"229","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=122","title":{"rendered":"\u7ebf\u6bb5\u6811"},"content":{"rendered":"

\u6982\u5ff5<\/h2>\n

\u7ebf\u6bb5\u6811\u662f\u7b97\u6cd5\u7ade\u8d5b\u4e2d\u5e38\u7528\u7684\u7528\u6765\u7ef4\u62a4 \u533a\u95f4\u4fe1\u606f<\/strong> \u7684\u6570\u636e\u7ed3\u6784\u3002<\/p>\n

\u7ebf\u6bb5\u6811\u53ef\u4ee5\u5728O(log N)<\/code>\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u5b9e\u73b0\u5355\u70b9\u4fee\u6539\u3001\u533a\u95f4\u4fee\u6539\u3001\u533a\u95f4\u67e5\u8be2\uff08\u533a\u95f4\u6c42\u548c\uff0c\u6c42\u533a\u95f4\u6700\u5927\u503c\uff0c\u6c42\u533a\u95f4\u6700\u5c0f\u503c\uff09\u7b49\u64cd\u4f5c\u3002<\/p>\n

\u64cd\u4f5c<\/h2>\n
    \n
  1. \u5b9a\u4e49\u6811<\/li>\n
  2. pushdown<\/li>\n
  3. pushup<\/li>\n
  4. build<\/li>\n
  5. modify<\/li>\n
  6. query<\/li>\n<\/ol>\n

    \u5b9a\u4e49\u6811<\/h3>\n
    struct node {\n    int l, r;\n    ll sum, add;\n} tr[N * 4]; \/\/\u7ecf\u8fc7\u63a8\u5bfc\uff0c\u9700\u8981\u5f00\u56db\u500d\n<\/code><\/pre>\n
    pushdown<\/h3>\n
    void pushdown(int u)\n{\n    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];\n    if (root.add) {\n        left.add += root.add, left.sum += ll(left.r - left.l + 1) * root.add;\n        right.add += root.add, right.sum += ll(right.r - right.l + 1) * root.add;\n        root.add = 0;\n    \/*\n    \u66f4\u65b0\u8fc7\u7a0b\u4e2d\u9700\u8981\u628a\u7236\u8282\u70b9\u7684\u61d2\u6807\u8bb0\u66f4\u65b0\u5230\u5b50\u8282\u70b9\n    \u5b50\u8282\u70b9\u7ee7\u627f\u7236\u8282\u70b9\u7684\u61d2\u6807\u8bb0\uff0c\u5e76\u66f4\u65b0\u81ea\u5df1\u7684sum\u503c\n    \u5220\u9664\u7236\u8282\u70b9\u7684\u61d2\u6807\u8bb0\n    *\/\n    }\n}<\/code><\/pre>\n
    pushup<\/h3>\n
    void pushup(int u)\n{\n    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;\n    \/\/\u5c06\u7236\u8282\u70b9\u7684sum\u66f4\u65b0\uff0c\u8bb0\u5f97\u8981\u76f4\u63a5=\uff0c\u800c\u4e0d\u662f+=\n}<\/code><\/pre>\n
    build<\/h3>\n
    void build(int u, int l, int r)\n{\n    if (l == r) {\n        tr[u] = { l, r, w[l], 0 };\n    } else {\n        tr[u] = { l, r };\n        int mid = (l + r) >> 1;\n        build(u << 1, l, mid);\n        build(u << 1 | 1, mid + 1, r);\n        pushup(u);\n    }\n}<\/code><\/pre>\n
    midify<\/h3>\n
    void modify(int u, int l, int r, int d)\n{\n    if (tr[u].l >= l && tr[u].r <= r) {\n        tr[u].sum += ll(tr[u].r - tr[u].l + 1) * d;\n        tr[u].add += d;\n    } else {\n        pushdown(u);\/\/\u56e0\u4e3a\u8981\u628a\u4e00\u4e2a\u533a\u95f4\u5206\u5f00\uff0c\u6240\u4ee5\u8981\u5f80\u4e0b\u7a7f\u61d2\u6807\u8bb0\n        int mid = (tr[u].l + tr[u].r) >> 1;\n        if (mid >= l)\n            modify(u << 1, l, r, d);\n        if (mid < r)\n            modify(u << 1 | 1, l, r, d);\n        pushup(u);\/\/\u4fee\u6539\u5b8c\u4ee5\u540e\u8981\u628a\u5b50\u8282\u70b9\u7684\u503c\u66f4\u65b0\u5230\u7236\u8282\u70b9\n    }\n}<\/code><\/pre>\n
    query<\/h3>\n
    ll query(int u, int l, int r)\n{\n\n    if (tr[u].l >= l && tr[u].r <= r)\n        return tr[u].sum;\n\n    ll sum = 0;\n    pushdown(u);\n    int mid = (tr[u].l + tr[u].r) >> 1;\n    if (l <= mid)\n        sum += query(u << 1, l, r);\n    if (mid < r)\n        sum += query(u << 1 | 1, l, r);\n\n    return sum;\n}<\/code><\/pre>\n
    \u4f8b\u9898<\/h2>\n
    \"image.png\"<\/p>\n
    \u4f8b\u9898\u94fe\u63a5<\/h3>\n
    \u94fe\u63a5<\/a><\/p>\n
    \u9898\u89e3<\/h3>\n
    #include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <unordered_map>\n#include <unordered_set>\n#include <vector>\n\nusing namespace std;\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\ntypedef long long ll;\ntypedef pair<ll, ll> pll;\ntypedef pair<int, int> pii;\ntypedef unsigned long long ull;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\nint n, m;\nint w[N];\nstruct node {\n    int l, r;\n    ll sum, add;\n} tr[N * 4];\n\nvoid pushdown(int u)\n{\n    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];\n    if (root.add) {\n        left.add += root.add, left.sum += ll(left.r - left.l + 1) * root.add;\n        right.add += root.add, right.sum += ll(right.r - right.l + 1) * root.add;\n        root.add = 0;\n    }\n}\n\nvoid pushup(int u)\n{\n    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;\n}\n\nvoid build(int u, int l, int r)\n{\n    if (l == r) {\n        tr[u] = { l, r, w[l], 0 };\n    } else {\n        tr[u] = { l, r };\n        int mid = (l + r) >> 1;\n        build(u << 1, l, mid);\n        build(u << 1 | 1, mid + 1, r);\n        pushup(u);\n    }\n}\n\nvoid modify(int u, int l, int r, int d)\n{\n    if (tr[u].l >= l && tr[u].r <= r) {\n        tr[u].sum += ll(tr[u].r - tr[u].l + 1) * d;\n        tr[u].add += d;\n    } else {\n        pushdown(u);\n        int mid = (tr[u].l + tr[u].r) >> 1;\n        if (mid >= l)\n            modify(u << 1, l, r, d);\n        if (mid < r)\n            modify(u << 1 | 1, l, r, d);\n        pushup(u);\n    }\n}\n\nll query(int u, int l, int r)\n{\n\n    if (tr[u].l >= l && tr[u].r <= r)\n        return tr[u].sum;\n\n    ll sum = 0;\n    pushdown(u);\n    int mid = (tr[u].l + tr[u].r) >> 1;\n    if (l <= mid)\n        sum += query(u << 1, l, r);\n    if (mid < r)\n        sum += query(u << 1 | 1, l, r);\n\n    return sum;\n}\n\nvoid solve()\n{\n    cin >> n >> m;\n    for (int i = 1; i <= n; i++)\n        cin >> w[i];\n\n    build(1, 1, n);\n    while (m--) {\n        char op;\n        int l, r, d;\n        cin >> op;\n        if (op == 'Q') {\n            cin >> l >> r;\n            cout << query(1, l, r) << endl;\n        } else {\n            cin >> l >> r >> d;\n            modify(1, l, r, d);\n        }\n    }\n}\nint main()\n{\n    \/\/ IOS;\n    int t = 1;\n    \/\/ cin >> t;\n    while (t--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
    \u6982\u5ff5 \u7ebf\u6bb5\u6811\u662f\u7b97\u6cd5\u7ade\u8d5b\u4e2d\u5e38\u7528\u7684\u7528\u6765\u7ef4\u62a4 \u533a\u95f4\u4fe1\u606f \u7684\u6570\u636e\u7ed3\u6784\u3002 \u7ebf\u6bb5\u6811\u53ef\u4ee5\u5728O(log N)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u5b9e\u73b0\u5355\u70b9\u4fee\u6539\u3001\u533a\u95f4\u4fee\u6539\u3001\u533a\u95f4\u67e5\u8be2\uff08\u533a\u95f4\u6c42\u548c\uff0c\u6c42\u533a\u95f4\u6700\u5927\u503c\uff0c\u6c42\u533a\u95f4\u6700\u5c0f\u503c\uff09\u7b49\u64cd\u4f5c\u3002 \u64cd\u4f5c \u5b9a\u4e49\u6811 pushdown pushup build modify query \u5b9a\u4e49\u6811 struct node { int l, r; ll sum, add; } tr[N * 4]; \/\/\u7ecf\u8fc7\u63a8\u5bfc\uff0c\u9700\u8981\u5f00\u56db\u500d pushdown void pushdown(int u) { auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1]; if (root.add) { left.add += root.add, […]<\/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":[49],"class_list":["post-122","post","type-post","status-publish","format-standard","hentry","category-acm","tag-49"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/122","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=122"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}