树状数组/分块/线段树

用树状数组完成 $O(\log n)$ 时间复杂度的区间查询 + 区间修改

直接上图

因此只需维护两个树状数组即可
一个是差分数组d[i]的树状数组tr[i]，还有一个是i*d[i]的树状数组tri[i]

Code(树状数组)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
int n, m;
int a[N];
LL tr[N], tri[N];
//tr[]数组是原始数组的差分数组d[i]的树状数组
//tri[]数组是原始数组的差分数组乘以i即i*d[i]的树状数组

int lowbit(int x)
{
    return x & -x;
}
void add(LL c[], int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i))
        c[i] += v;
}
LL query(LL c[], int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += c[i];
    return res;
}
//对应最后一步推导的公式
LL get_sum(int x)
{
    return query(tr, x) * (x + 1) - query(tri, x);
}
int main()
{
    scanf("%d%d", &n, &m);
    //输入数组a[i]
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    //先构造两个数组 d[i] 和 i*d[i]
    for (int i = 1; i <= n; ++i) 
        tr[i] = a[i] - a[i - 1], tri[i] = tr[i] * i;
    //原地 O(n) 建树状数组
    for (int x = 1; x <= n; ++x)
        for (int i = x - 1; i >= x - lowbit(x) + 1; i -= lowbit(i))
            tr[x] += tr[i], tri[x] += tri[i];
    //读入查询
    while (m--)
    {
        char op[2];
        int l, r, c;
        scanf("%s", op);
        if (op[0] == 'Q')
        {
            scanf("%d%d", &l, &r);
            printf("%lld\n", get_sum(r) - get_sum(l - 1));
        }
        else
        {
            scanf("%d%d%d", &l, &r, &c);
            add(tr, l, c), add(tr, r + 1, -c);
            add(tri, l, l * c), add(tri, r + 1, (r + 1) * -c);
        }
    }
    return 0;
}

Code（分块）$O(m\sqrt{n})$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = 350;

int n, m, len;
LL sum[M], flag[M]; //sum：块的总和；flag：块的懒标记
int w[N];

int get(int i)
{
    return i / len;
}
void modify(int l, int r, int d)
{
    if (get(l) == get(r))   //段内直接暴力
    {
        for (int i = l; i <= r; i ++ )
            w[i] += d, sum[get(i)] += d;
    }
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) w[i] += d, sum[get(i)] += d, i ++ ;
        while (get(j) == get(r)) w[j] += d, sum[get(j)] += d, j -- ;
        for (int k = get(i); k <= get(j); k ++ ) sum[k] += len * d, flag[k] += d;
    }
}
LL query(int l, int r)
{
    LL res = 0;
    if (get(l) == get(r))   //段内直接暴力
    {
        for (int i = l; i <= r; i ++ )
            res += w[i] + flag[get(i)];
    }
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) res += w[i] + flag[get(i)], i ++ ;
        while (get(j) == get(r)) res += w[j] + flag[get(j)], j -- ;
        for (int k = get(i); k <= get(j); k ++ ) res += sum[k];
    }
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w[i]);
        sum[get(i)] += w[i];
    }

    char op[2];
    int l, r, d;

    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            modify(l, r, d);
        }
        else printf("%lld\n", query(l, r));
    }
    return 0;
}

线段树 $O(m\log n)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;

const int N = 1e5 + 10;
int n, m;
int w[N];
struct Node
{
    int l, r;
    LL sum, add;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        //传递懒标记，更新子树
        left.add += root.add, left.sum += (LL) (left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (LL) (right.r - right.l + 1) * root.add;
        //删除父结点懒标记
        root.add = 0;
    }
}
void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[l], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int l, int r, int v)
{
    if (l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
        tr[u].add += v;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, v);
        if (r > mid) modify(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
LL query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v += query(u << 1 | 1, l, r);
    return v;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    build(1, 1, n);

    char op[2];
    int l, r, t;
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q') printf("%lld\n", query(1, l, r));
        else
        {
            scanf("%d", &t);
            modify(1, l, r, t);
        }
    }
    return 0;
}