P3374 【模板】树状数组 1和2（洛谷）

谁借莪１个温暖的怀抱￠ 2021-07-16 12:34 302阅读 0赞

[模板1题目][1]

Code:

#include<iostream>
    #include<string>
    #include<memory.h>
    typedef long long ll;
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    //#define int long long
    using namespace std;
    ll a, b, x, y, ans;
    struct node
    { 
        ll l, r, w, f;
    }tree[500005*4];
    inline void build(int k, int ll, int rr)//建树 
    { 
        tree[k].l = ll, tree[k].r = rr;
        if (tree[k].l == tree[k].r)
        { 
            cin>>tree[k].w;
            return;
        }
        int m = (ll + rr) / 2;
        build(k * 2, ll, m);
        build(k * 2 + 1, m + 1, rr);
        tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    inline void down(int k)//标记下传 
    { 
        tree[k * 2].f += tree[k].f;
        tree[k * 2 + 1].f += tree[k].f;
        tree[k * 2].w += tree[k].f * (tree[k * 2].r - tree[k * 2].l + 1);
        tree[k * 2 + 1].w += tree[k].f * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1);
        tree[k].f = 0;
    }
    inline void ask_interval(int k)//区间查询 
    { 
        if (tree[k].l >= a && tree[k].r <= b)
        { 
            ans += tree[k].w;
            return;
        }
        if (tree[k].f) down(k);
        int m = (tree[k].l + tree[k].r) / 2;
        if (a <= m) ask_interval(k * 2);
        if (b > m) ask_interval(k * 2 + 1);
    }
    inline void change_point(int k)//单点修改 
    { 
        if (tree[k].l == tree[k].r)
        { 
            tree[k].w += y;
            return;
        }
        if (tree[k].f) down(k);
        int m = (tree[k].l + tree[k].r) / 2;
        if (x <= m) change_point(k * 2);
        else change_point(k * 2 + 1);
        tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    
    int main()
    { 
        FAST;
        int n, m;
        cin >> n >> m;
        build(1, 1, n);
        for (int i = 1;i <= m;i++)
        { 
            int t;cin >> t;
            if (t == 1)
            { 
                cin >> x >> y;
                change_point(1);
            }
            else
            { 
                ans = 0;cin >> a >> b;
                ask_interval(1);
                cout << ans << endl;
            }
        }
    }

[模板二题目][Link 1]

#include<iostream>
    #include<string>
    #include<memory.h>
    typedef long long ll;
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    //#define int long long
    using namespace std;
    ll a, b, x, y, ans;
    struct node
    { 
        ll l, r, w, f;
    }tree[5000005];
    inline void build(int k, int ll, int rr)//建树 
    { 
        tree[k].l = ll, tree[k].r = rr;
        if (tree[k].l == tree[k].r)
        { 
            cin>>tree[k].w;
            return;
        }
        int m = (ll + rr) / 2;
        build(k * 2, ll, m);
        build(k * 2 + 1, m + 1, rr);
        tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    inline void down(int k)//标记下传 
    { 
        tree[k * 2].f += tree[k].f;
        tree[k * 2 + 1].f += tree[k].f;
        tree[k * 2].w += tree[k].f * (tree[k * 2].r - tree[k * 2].l + 1);
        tree[k * 2 + 1].w += tree[k].f * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1);
        tree[k].f = 0;
    }
    inline void ask_point(int k)//单点查询
    { 
        if (tree[k].l == tree[k].r)
        { 
            ans = tree[k].w;
            return;
        }
        if (tree[k].f) down(k);
        int m = (tree[k].l + tree[k].r) / 2;
        if (x <= m) ask_point(k * 2);
        else ask_point(k * 2 + 1);
    }
    inline void change_point(int k)//单点修改 
    { 
        if (tree[k].l == tree[k].r)
        { 
            tree[k].w += y;
            return;
        }
        if (tree[k].f) down(k);
        int m = (tree[k].l + tree[k].r) / 2;
        if (x <= m) change_point(k * 2);
        else change_point(k * 2 + 1);
        tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    inline void ask_interval(int k)//区间查询 
    { 
        if (tree[k].l >= a && tree[k].r <= b)
        { 
            ans += tree[k].w;
            return;
        }
        if (tree[k].f) down(k);
        int m = (tree[k].l + tree[k].r) / 2;
        if (a <= m) ask_interval(k * 2);
        if (b > m) ask_interval(k * 2 + 1);
    }
    inline void change_interval(int k)//区间修改 
    { 
        if (tree[k].l >= a && tree[k].r <= b)
        { 
            tree[k].w += (tree[k].r - tree[k].l + 1) * y;
            tree[k].f += y;
            return;
        }
        if (tree[k].f) down(k);
        int m = (tree[k].l + tree[k].r) / 2;
        if (a <= m) change_interval(k * 2);
        if (b > m) change_interval(k * 2 + 1);
        tree[k].w = tree[k * 2].w + tree[k * 2 + 1].w;
    }
    
    int main()
    { 
        FAST;
        int n, m;
        cin >> n >> m;
        build(1, 1, n);
        for (int i = 1;i <= m;i++)
        { 
            int t;cin >> t;
            if (t == 1)
            { 
                cin >> a >> b >> y;
                change_interval(1);
            }
            else
            { 
                cin >> x;
                ans = 0;
                ask_point(1);
                cout << ans << endl;
            }
        }
    }

[1]: https://www.luogu.com.cn/problem/P3374
[Link 1]: https://www.luogu.com.cn/problem/P3368