Lazy Tag 查询Sum && 区间更新

1.Lazy Tag 查询Sum

void pushdown(int sn) {
    if (node[sn].add != 0) {
        node[sn * 2].add += node[sn].add;
        node[sn * 2 + 1].add += node[sn].add;
        node[sn * 2].sum += node[sn].add * (node[sn * 2].r - node[sn * 2].l + 1);
        node[sn * 2 + 1].sum += node[sn].add * (node[sn * 2 + 1].r - node[sn * 2 + 1].l + 1);
        node[sn].add = 0;
    }
}

//查询sum
ll query(int sn, int l, int r) {
    if (node[sn].l == l && node[sn].r == r) {
        return node[sn].sum;
    }
    pushdown(sn);
    int mid = node[sn].mid();
    if (r <= mid)
        return query(sn * 2, l, r);
    else if (l > mid)
        return query(sn * 2 + 1, l, r);
    else {
        return query(sn * 2, l, mid) +
               query(sn * 2 + 1, mid + 1, r);
    }
}

二、区间更新

//查询sum
ll query(int sn, int l, int r) {
    if (node[sn].l == l && node[sn].r == r) {
        return node[sn].sum;
    }
    pushdown(sn);
    int mid = node[sn].mid();
    if (r <= mid)
        return query(sn * 2, l, r);
    else if (l > mid)
        return query(sn * 2 + 1, l, r);
    else {
        return query(sn * 2, l, mid) +
               query(sn * 2 + 1, mid + 1, r);
    }
}

整体代码：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include <set>

using namespace std;
#define ll long long
//Lazy Tag  查询sum

const int maxn = 2e5 + 10;

ll a[maxn] = {0};

struct Node {
    int l, r;
    ll sum, add;

    int mid() {
        return (l + r) / 2;
    }
} node[maxn * 4];

void build(int sn, int l, int r) {
    node[sn].l = l;
    node[sn].r = r;
    if (l == r) {
        node[sn].sum = a[l];
        return;
    }
    int mid = (node[sn].l + node[sn].r) / 2;
    build(sn * 2, l, mid);
    build(sn * 2 + 1, mid + 1, r);
    node[sn].sum = node[sn * 2].sum + node[sn * 2 + 1].sum;
}

void pushdown(int sn) {
    if (node[sn].add != 0) {
        node[sn * 2].add += node[sn].add;
        node[sn * 2 + 1].add += node[sn].add;
        node[sn * 2].sum += node[sn].add * (node[sn * 2].r - node[sn * 2].l + 1);
        node[sn * 2 + 1].sum += node[sn].add * (node[sn * 2 + 1].r - node[sn * 2 + 1].l + 1);
        node[sn].add = 0;
    }
}

void update(int sn, int l, int r, int change) {
    if (node[sn].l == l && node[sn].r == r) {
        node[sn].add += change;
        node[sn].sum += (node[sn].r - node[sn].l + 1) * change;
        return;
    }
    pushdown(sn);
    int mid = (node[sn].l + node[sn].r) / 2;
    if (r <= mid) update(sn * 2, l, r, change);
    else if (l > mid) update(sn * 2 + 1, l, r, change);
    else {
        update(sn * 2, l, mid, change);
        update(sn * 2 + 1, mid + 1, r, change);
    }
    node[sn].sum = node[sn * 2].sum + node[sn * 2 + 1].sum;
}

//查询sum
ll query(int sn, int l, int r) {
    if (node[sn].l == l && node[sn].r == r) {
        return node[sn].sum;
    }
    pushdown(sn);
    int mid = node[sn].mid();
    if (r <= mid)
        return query(sn * 2, l, r);
    else if (l > mid)
        return query(sn * 2 + 1, l, r);
    else {
        return query(sn * 2, l, mid) +
               query(sn * 2 + 1, mid + 1, r);
    }
}

char c[10];

int main() {

    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);

    while (m--) {
        scanf("%s", c);
        if (c[0] == 'C') {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            update(1, x, y, z);
        } else if (c[0] == 'Q') {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, x, y));
        }
    }
    return 0;
}