线段树模板

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <functional>
#include <map>
#include <set>
#include <stack>
#define FT(a, b) memset(a, b, sizeof(a))
#define FAT(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
const int M = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = 3.1415926535;
struct node
{
    int l, r;
    ll sum;
    int lazy;
} tree[M * 4];
int n, m;
void push_up(int root)
{
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}
void build(int root, int l, int r)
{
    tree[root] = {l, r, 0, 0};
    if (l == r)
    {
        scanf("%lld", &tree[root].sum);
    }
    else
    {
        int mid = l + r >> 1;
        build(root << 1, l, mid), build(root << 1 | 1, mid + 1, r);
        push_up(root);
    }
}
void push_down(int root)
{
    auto &l = tree[root << 1], &r = tree[root << 1 | 1];
    l.sum += (l.r - l.l + 1) * tree[root].lazy;
    r.sum += (r.r - r.l + 1) * tree[root].lazy;
    l.lazy += tree[root].lazy;
    r.lazy += tree[root].lazy;
    tree[root].lazy = 0;
}
void modify(int root, int l, int r, int x)
{
    if (tree[root].l >= l && tree[root].r <= r)
    {
        tree[root].sum += (tree[root].r - tree[root].l + 1) * x;
        tree[root].lazy += x;
    }
    else
    {
        push_down(root);
        int mid = tree[root].l + tree[root].r >> 1;
        if (l <= mid)
            modify(root << 1, l, r, x);
        if (r > mid)
            modify(root << 1 | 1, l, r, x);
        push_up(root);
    }
}
ll query(int root, int l, int r)
{
    if (tree[root].l >= l && tree[root].r <= r)
    {
        return tree[root].sum;
    }
    push_down(root);
    int mid = tree[root].l + tree[root].r >> 1;
    ll sum = 0;
    if (l <= mid)
        sum += query(root << 1, l, r);
    if (r > mid)
        sum += query(root << 1 | 1, l, r);
    return sum;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("D:\\code\\c++\\in.txt", "r", stdin);
#endif
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--)
    {
        char s[2];
        int l, r;
        scanf("%s%d%d", s, &l, &r);
        if (*s == ‘Q‘)
        {
            printf("%lld\n", query(1, l, r));
        }
        else
        {
            int d;
            scanf("%d", &d);
            modify(1, l, r, d);
        }
    }
    return 0;
}