一个简单的整数问题2_第一行:输入两个数 n,q,表示给定数组的长度和操作数 第二行:输入n个数,表示长度为

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 数列中第 l~r 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式
第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤1000000000

输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例：
4
55
9
15
1
2
3
4
5
6
7
8
9
10
11
12
13

线段树

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 1e5 + 10;
struct T {
    int l, r;
    ll sum, add;
#define l(x) t[x].l
#define r(x) t[x].r
#define s(x) t[x].sum
#define a(x) t[x].add
} t[N * 4];
int a[N], n, m;

inline void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if (l == r) {
        s(p) = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    s(p) = s(p << 1) + s(p << 1 | 1);
}

inline void spread(int p) {
    if (a(p)) {
        s(p << 1) += a(p) * (r(p << 1) - l(p << 1) + 1);
        s(p << 1 | 1) += a(p) * (r(p << 1 | 1) - l(p << 1 | 1) + 1);
        a(p << 1) += a(p);
        a(p << 1 | 1) += a(p);
        a(p) = 0;
    }
}

void change(int p, int l, int r, int d) {
    if (l(p) >= l && r(p) <= r) {
        s(p) += 1ll * d * (r(p) - l(p) + 1);
        a(p) += d;
        return;
    }
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    if (l <= mid)change(p << 1, l, r, d);
    if (r > mid)change(p << 1 | 1, l, r, d);
    s(p) = s(p << 1) + s(p << 1 | 1);
}

ll ask(int p, int l, int r) {
    if (l(p) >= l && r(p) <= r)return s(p);
    spread(p);
    int mid = (l(p) + r(p)) >> 1;
    ll res = 0;
    if (l <= mid)res += ask(p << 1, l, r);
    if (r > mid)res += ask(p << 1 | 1, l, r);
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
    build(1, 1, n);
    char op;
    int l, r, d;
    while (m--) {
        cin >> op;
        scanf("%d%d", &l, &r);
        if (op == 'C') {
            scanf("%d", &d);
            change(1, l, r, d);
        } else printf("%lld\n", ask(1, l, r));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

树状数组

#include<bits/stdc++.h>

#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 1e5 + 10;
ll c[2][N], a[N];
int n, m;

inline ll ask(int k, int x) {
    ll res = 0;
    for (; x; x -= lowbit(x))
        res += c[k][x];
    return res;
}

inline void add(int x, int d) {
    for (int y = x; y <= n; y += lowbit(y))
        c[0][y] += d, c[1][y] += x * d;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), a[i] += a[i - 1];
    for (int i = 1; i <= m; i++) {
        char q;
        cin >> q;
        if (q == 'Q') {
            int l, r;
            scanf("%d%d", &l, &r);
            ll ans = (a[r] + (r + 1) * ask(0, r) - ask(1, r)) - (a[l - 1] + l * ask(0, l - 1) - ask(1, l - 1));
            printf("%lld\n", ans);
        } else {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            add(l, d), add(r + 1, -d);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

分块

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll a[N], sum[N], add[N];
int L[N], R[N], pos[N];
int n, m, t;

inline void build() {
    t = sqrt(n);
    for (int i = 1; i <= t; i++) {
        L[i] = (i - 1) * t + 1;
        R[i] = i * t;
    }
    if (R[t] < n)t++, L[t] = R[t - 1] + 1, R[t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++)
            pos[j] = i, sum[i] += a[j];
}

inline void change(int l, int r, ll d) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++)a[i] += d;
        sum[p] += d * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; i++)add[i] += d;
        for (int i = l; i <= R[p]; i++)a[i] += d;
        sum[p] += (R[p] - l+1) * d;
        for (int i = L[q]; i <= r; i++)a[i] += d;
        sum[q] += (r - L[q] + 1) * d;
    }
}

inline ll ask(int l, int r) {
    int p = pos[l], q = pos[r];
    ll ans = 0;
    if (p == q) {
        for (int i = l; i <= r; i++)
            ans += a[i];
        ans += add[p] * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; i++)
            ans += sum[i] + add[i] *(R[i]-L[i]+1);
        for (int i = l; i <= R[p]; i++)ans += a[i];
        ans += (R[p] - l + 1) * add[p];
        for (int i = L[q]; i <= r; i++)ans += a[i];
        ans += (r - L[q] + 1) * add[q];
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
    build();
    char op;
    int l, r;
    while (m--) {
        cin >> op;
        scanf("%d%d", &l, &r);
        if (op == 'C') {
            ll d;
            scanf("%lld", &d);
            change(l, r, d);
        } else printf("%lld\n", ask(l, r));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70