A Simple Problem with Integers（线段树区间更新模板）

最基本的线段树的区间更新及查询和

用tag(lazy)数组来“延缓”更新，查询或添加操作必须进行pushdown操作，即把tag从p传到lp和rp并清楚tag[p]，既然得往lp和rp递归，那么就可以“顺便”往下传

pushdown操作代码

inline void pushdown(int p, int llen, int rlen) {

    if (tag[p]) {

        tag[lp] += tag[p], tag[rp] += tag[p];

        tree[lp] += tag[p] * llen;

        tree[rp] += tag[p] * rlen;

        tag[p] = ;

    }

}

还要注意必须用long long来存值

代码如下

#include <cstdio>

#include <algorithm>

#define ll long long

#define lp p<<1

#define rp p<<1|1

using namespace std;

const int maxn = ;

ll tree[maxn<<], tag[maxn<<];

void build(int p, int l, int r) {

    if (l == r) {

        scanf("%lld", &tree[p]);

        return;

    }

    int mid = (l + r) >> ;

    build(lp, l, mid); build(rp, mid + , r);

    tree[p] = tree[lp] + tree[rp];

}

inline void pushdown(int p, int llen, int rlen) {

    if (tag[p]) {

        tag[lp] += tag[p], tag[rp] += tag[p];

        tree[lp] += tag[p] * llen;

        tree[rp] += tag[p] * rlen;

        tag[p] = ;

    }

}

void add(int p, int l, int r, int x, int y, int z) {

    if (x <= l && y >= r) {

        tag[p] += 1LL * z;

        tree[p] += 1LL * z * (r - l + );

        return;

    }

    int mid = (l + r) >> ;

    pushdown(p, mid - l + , r - mid);

    if (x <= mid) add(lp, l, mid, x, y, z);

    if (y > mid) add(rp, mid + , r, x, y, z);

    tree[p] = tree[lp] + tree[rp];

}

ll find(int p, int l, int r, int x, int y) {

    if (x <= l && y >= r) return tree[p];

    int mid = (l + r) >> ;

    pushdown(p, mid - l + , r - mid);

    if (y <= mid) return find(lp, l, mid, x, y);

    if (x > mid) return find(rp, mid + , r, x, y);

    return find(lp, l, mid, x, y) + find(rp, mid + , r, x, y);

}

int main() {

    int n, q;

    scanf("%d%d", &n, &q);

    build(, , n);

    while (q--) {

        char s[];

        int x, y;

        scanf("%s%d%d", s, &x, &y);

        if (s[] == 'Q') {

            printf("%lld\n", find(, , n, x, y));

        } else {

            int z; scanf("%d", &z);

            add(, , n, x, y, z);

        }

    }

    return ;

}

巴特西

A Simple Problem with Integers（线段树区间更新模板）

最新文章

热门文章